冒泡排序(Bubble Sort)

算法思想：

重复地遍历待排序的数列，遍历的过程中一次比较两个元素，一遍遍历结束后，确定一个元素的位置。对待排序重复上述操作；

算法步骤：

1.比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；3.针对所有的元素重复以上的步骤，除了最后一个；
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubble_sort(a_list: list):
    length = len(a_list)
    # 每次循环排出一个最大值，共需要n-1次
    for i in range(length - 1):
        # 排出当前最大值共需比较length-i-1次
        for j in range(1, length - i):
            if a_list[j - 1] > a_list[j]:
                a_list[j - 1],a_list[j] = a_list[j], a_list[j-1]


l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list=l)
print(l)

插入排序(Insertion Sort)

算法思想：

从待排序的序列中取出元素在已排序的序列中找到插入的位置。

算法步骤：

1.初始有序列表中包含一个元素；
2.从待排序列表中依次选择一个元素和已排序列表中的元素从后往前比较；
3.顺序不对，就交换元素位置，直到找到最合适的位置插入即可；

def insert_sort(a_list: list):
    length = len(a_list)
    # 每次循环排出一个最小值到开头，共需n-1次。
    for i in range(1, length):
        # 倒序遍历已排序的前半序列，将本次待排序的元素插入指定位置
        for j in range(i, 0, -1):
            if a_list[j] < a_list[j - 1]:
                # 同时对两个元素进行赋值，交换了值，免去了使用中间变量。
                a_list[j], a_list[j - 1] = a_list[j - 1], a_list[j]


l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insert_sort(l)
print(l)

选择排序(Selection sort)

算法思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

算法步骤：

1.首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，
2.然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
3.选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,
4.它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

def select_sort(a_list: list):
    length = len(a_list)
    # 每次循环从待排序序列中选出一个最小值，放到已排序末尾，共需n-1次。
    for i in range(length - 1):
        min_index = i
        # 遍历待排序序列，从中选出最小值的位置
        for j in range(i + 1, length):
            if a_list[min_index] > a_list[j]:
                min_index = j
        # 交换待排序最小值和待排序头元素的位置        
        a_list[i], a_list[min_index] = a_list[min_index], a_list[i]

l = [54, 226, 93, 17, 77, 31, 44, 55, 20]
select_sort(a_list=l)
print(l)

希尔排序(Shell Sort)

算法思想：

是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL,Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着下标增量逐渐减少,每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组,算法便终止。

算法步骤

1.将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列(步长更短了，列数更少了)来进行。
2.最后整个表就只有一列了,使用直接插入排序。
3.将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

def shell_sort(a_list: list):
    n = len(a_list)
    # 初始步长
    step = n // 2
    #
    while step > 0:
        # 插入排序
        for i in range(step):
            for j in range(i, n, step):
                for k in range(j, 0, -step):
                    if a_list[k - step] > a_list[k]:
                        a_list[k - step], a_list[k] = a_list[k], a_list[k - step]

        # 更新步长
        step //= 2


l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shell_sort(a_list=l)
print(l)

"""
step：5
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

排序后
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

step：3
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序后
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

step：1
直接插入排序
"""

堆排序(Heap Sort)

算法思想：堆排序是选择排序的一种,逻辑上使用完全二叉树存储,物理上使用数组存储。分为大顶堆和小顶堆，大顶堆。满足所有父节点的值都大于子节点值的堆记为大顶堆;满足所有父节点得值都小于子节点值的堆记为小顶堆;父子节点之间的索引存在着对应的关系,假设父节点索引为i,子节点存在的话索引为2i+1和2i+2.

算法步骤：

1.首先进行堆的初始化,以大顶堆为例, 依次检查完全二叉树的所有非叶子节点是否满足大顶堆的性质,如若不满足需要交换元素;
2.其次交换队首和队尾元素,相当于取出最大值,然后将剩下的完全二叉树继续维护其大顶堆性质;
3.重复上述过程;

特点

1.完全二叉树倒数第一个非叶子节点的索引为(length)//2.
2.完全二叉树父子节点的索引映射关系: 父节点索引为i,左孩子索引为2i+1,右孩子索引为2i+2;
3.大顶堆排序的结果是升序，小顶堆排序的结果是降序。

# 大顶堆
def max_heap_sort(input_list):
    def maintain_heap(input_list, parent, length):
        # 根节点的左孩子索引
        child = 2 * parent + 1
        while child < length:
            # 更新孩子索引为左右最大孩子节点的索引
            if child + 1 < length and input_list[child] < input_list[child + 1]:
                child += 1
            # 当前父节点是否满足最大堆的性质
            if input_list[parent] >= input_list[child]:
                break
            # 不满足的话,更新父节点的值为最大的孩子节点值
            input_list[parent], input_list[child] = (
                input_list[child],
                input_list[parent],
            )
            parent = child
            child = 2 * parent + 1

    sorted_list = input_list
    length = len(sorted_list)
    # 首先初始化大顶堆,循环依次检查每一个非叶子节点是否满足大顶堆的性质
    for i in range(length // 2)[::-1]:
        maintain_heap(sorted_list, i, length)
    # 堆排序
    for j in range(1, length)[::-1]:
        sorted_list[j], sorted_list[0] = sorted_list[0], sorted_list[j]

        maintain_heap(sorted_list, 0, j)
        print(f"第{length - j}趟排序:", end="")
        print(sorted_list)
    return sorted_list

# 小顶堆
def min_heap_sort(input_list):
    def main_heap(input_list, parent, length):
        child = 2 * parent + 1
        while child < length:
            if child + 1 < length and input_list[child] > input_list[child + 1]:
                child += 1
            if input_list[parent] <= input_list[child]:
                break
            input_list[parent], input_list[child] = (
                input_list[child],
                input_list[parent],
            )
            parent = child
            child = 2 * parent + 1

    length = len(input_list)
    for i in range(length // 2)[::-1]:
        main_heap(input_list, i, length)

    for i in range(1, length)[::-1]:
        input_list[0], input_list[i] = input_list[i], input_list[0]
        main_heap(input_list, 0, i)
        print(f"第{length-i}次排序", end="")
        print(input_list)
    return input_list

if __name__ == "__main__":
    test_case1 = [6, 4, 8, 9, 2, 3, 1]
    test_case2 = [100, 5, 3, 11, 6, 8, 7]
    test_case3 = [1, 3, 4, 5, 2, 6, 9, 7, 8, 0]
    print("排序前:", test_case3)
    sorted_list = max_heap_sort(test_case3)
    print("排序后:", sorted_list)
    # print("排序前:", test_case1)
    # sorted_list = min_heap_sort(test_case1)
    # print("排序后:", sorted_list)

归并排序(Merge sort)

算法思想：

采用分治法对数组划分为小单位，然后依次将相邻小单位排序合并；依次合并所有的较有序单位得到最终的序列；

算法步骤：

1.以二分归并为例，首先不停地将数组分组，直到组长为1；
2.开始排序并合并相邻的小组和大组；
3.依次回溯分组的过程，最后变成有序大组；

def merge_sort(a_list: list):
    if len(a_list) == 1:
        return a_list
    # 二分分解
    num = len(a_list) // 2
    left = merge_sort(a_list=a_list[:num])
    right = merge_sort(a_list=a_list[num:])
    # 合并左右两数组
    return merge(left, right)


def merge(left: list, right: list):
    result = []
    print(f"{left}和{right}",end='')
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if not left:
        result.extend(right)
    else:
        result.extend(left)
    print(f"合并后{result}")
    return result


l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
sorted_l = merge_sort(a_list=l)
print(sorted_l)

归并的过程.png

快速排序(Quicksort)

算法思想：

也是基于分治思想，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法步骤：

1.从数列中挑出一个元素，称为"基准"(pivot);
2.分区(partition)操作:重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置;
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.

def quick_sort(a_list: list, start: int, end: int):
    # 递归的推出条件
    if start >= end:
        return

    pivot = a_list[start]
    low, high = start, end
    # low, high 游标未重合
    while low < high:
        # 当high所指元素大于等于pivot,high--
        while low < high and a_list[high] >= pivot:
            high -= 1
        # 把右边小于pivot值更新到low位置。
        a_list[low] = a_list[high]
        # low所指元素小于等于pivot
        while low < high and a_list[low] <= pivot:
            low += 1
        # 把左边大于pivot值更新到high位置。
        a_list[high] = a_list[low]
    # 退出循环后，low与high重合，此时所指位置为pivot的正确位置
    a_list[low] = pivot
    print(f"{a_list}")
    # 对pivot元素左边的子序列进行快速排序
    quick_sort(a_list=a_list, start=start, end=low - 1)
    # 对pivot元素右边的子序列进行快速排序
    quick_sort(a_list=a_list, start=low + 1, end=end)


l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(l, 0, len(l) - 1)
print(l)

可以看出，每次排序找到一个元素最终位置。

快速排序的过程png

基数排序(Radix sort)

算法思想：

从数据由低到高位或者由高位到低位，进行分桶排序的过程；

算法步骤

这里以最低有效位为例
1.取得数组中的最大数，并取得位数；
2.对数位较短的数前面补零；
3.分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中;
4.收集，再将放置在0~9号桶中的数据按顺序放到数组中;
5.重复3~4过程，直到最高位，即可完成排序。

def max_radix_sort(input_list):
    d = len(str(max(input_list)))
    for i in range(d):
        bucks = [[] for _ in range(10)]
        for j in input_list:
            bucks[j // 10**i % 10].append(j)

        input_list = [k for buck in bucks for k in buck]
        print(input_list)
    return input_list


def min_radix_sort(input_list):
    d = len(str(max(input_list)))
    for i in range(d):
        bucks = [[] for _ in range(10)]
        for j in input_list:
            bucks[j // 10**i % 10].append(j)

        input_list = [k for buck in bucks[::-1] for k in buck]
        print(input_list)
    return input_list


if __name__ == "__main__":
    test_case = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]
    print(f"升序排序前：{test_case}")
    sorted_list = max_radix_sort(test_case)
    print(f"升序排序后：{sorted_list}")
    print(f"降序排序前：{test_case}")
    sorted_list = min_radix_sort(test_case)
    print(f"降序排序后：{sorted_list}")

可以看到每次排序后，结果对应数位值按照有序的排列

基数排序的过程.png

总结

八种排序算法总结.png