经典排序方法（python），希尔排序，归并排序，快速排序，计数排序

希尔排序

思路：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序

代码：

# 希尔排序 记录间隔多少元素 len//2 然后比较相隔元素的大小，交换位置
def shell_sort(num:list[int]) -> None:
    length = len(num) #长度
    gap = length // 2
    while gap > 0:
        for i in range(gap, length):
            temp = num[i] #记录中间元素值
            j = i
            while j >= gap and num[j] < num[j-gap]:
                num[j] = num[j - gap]
                j -= gap
                num[j] = temp
        gap = gap // 2

总结：不断的间隔一定元素比较排序

归并排序

思路：

• 把长度为n的输入序列分成两个长度为n/2的子序列，直到每个数字分为一组；
• 将若干个组两两合并，保证合并后的组是有有序的；
• 重复第2步操作直到只剩一组，排序完成

代码：

# 归并排序 先分后和，递归思想
def merge_sort(num: list[int]) -> list[int]:
    length = len(num)
    if length <= 1:
        return num
    mid = length // 2
    left = merge_sort(num[:mid])
    right = merge_sort(num[mid:])
    return merge(left, right)


def merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result

 总结：先分后和，在不断合并的过程中序列已经有序

快速排序

思路：

• 从数列中挑出一个元素，称为 “基准”
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作
• 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

代码：

# 快速排序
def quick_sort(num: list[int]) -> list[int]:
    length = len(num)
    left, right = [], []
    if length >= 2:
        mid = num[length//2]
        num.remove(mid)
        for i in num:
            if i <= mid:
                left.append(i)
            else:
                right.append(i)
        return quick_sort(left) + [mid] + quick_sort(right)
    else:
        return num

总结：相当于冒泡排序的升级版，在不断和中间值比较的过程中完成排序

计数排序

思路：

• 根据待排序集合中最大元素和最小元素的差值范围，申请额外的地址空间；
• 遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内（对应的列表索引）；
• 对额外空间内数据进行计算，得出每一个元素的正确位置；
• 将待排序集合每一个元素移动到计算得出的正确位置上

代码：

# 计数排序
def count_sort(num: list[int]) -> None:
    if len(num) <= 1:
        return num
    min_val = min(num)  #记录序列最小值
    max_val = max(num)  #记录序列最大值
    count = max_val - min_val + 1
    addr = [0 for _ in range(count)]  # 需要开辟的地址空间
    for i in num:  # 将排序的值分别在对应的索引位置计数
        addr[i-min_val] += 1
    num.clear()
    for idx, val in enumerate(addr):  #遍历-排序
        for _ in range(val):
            num.append(idx+min_val)

总结：这种思想很巧妙，将要排序的序列值，记录在新开辟空间的对应的索引位置上，然后再遍历新开辟空间中的序列，得到正确得排序对象，缺陷可能在于数据之间的差值太大，容易造成空间浪费或者溢出