排序算法

排序算法

排序算法就是将一组数据中的每个元素按照特定的顺序排序。 常见的排序算法很多，死记硬背不可取，熟悉原理吾所取。

1. 冒泡算法 bubble sort

循环数组每次选两个数比较，将较小的放置到前面，慢慢地将小的"浮出水面"。 冒泡排序的时间复杂度最差为\(O(n^2)\)，最好为\(O(n)\)；空间复杂度为\(O(1)\)。

def bubble_sort(arr: list) -> list:
    # 注意循环的起始和终止位置
    # 如果i=0, 会导致j+1超过数组元素长度
    # 保证 j 和 j+1 能正常索引
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            # 比较大小
            if arr[j] > arr[j+1]:
                # 浮出水面操作
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

2. 选择排序 selection sort

选择排序, 最直观，直接在数组中找。 - 第一步，在数组中选择最小的元素放置到排序的起始位置， - 第二步，在剩余的元素中继续寻找最小元素，然后放置到已经排序的序列末尾 - 第三步，重复第二步

选择排序的时间复杂度最差\(O(n^2)\)，最好为\(O(n^2)\)；空间复杂度为\(O(1)\)

def select_sort(arr: list) -> list:
    # 首先循环数组，指定第一个为最小索引
    for i in range(len(arr) - 1):
        # 记录最小索引
        minIndex = i
        # 遍历剩下的元素
        for j in range(i, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # 如果i 不是最小值的索引，交换i和minIndex交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

3. 插入排序 insertion sort

与打扑克牌的原理类似，它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分， 每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。 插入排序的时间复杂度最高为\(O(n^2)\)，即原始数组倒序排列。 时间复杂度最好为\(O(n)\)，空间复杂度为\(O(1)\)。

• 算法稳定性 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！ 插入排序是稳定的。

def insert_sort(arr: list) -> list:
    # 循环数组
    for i in range(len(arr)):
        preIndex = i - 1 # 前一个索引
        current = arr[i] # 保存当前值
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex] # 交换，将前一位的值换到后一位
            preIndex -= 1                   # 索引-1，继续交换；直到换到最前面，preIndex<0停止操作
        arr[preIndex+1] = current           # 当前值的位置
        print(i, arr)
    return arr
# 当i=0时，数组保持原样

# 当i=1时，current = arr[1]
#          preIndex = 0,  如果arr[0] > current, arr[1] = arr[0], preIndex=-1;
# 退出循环,preIndex = -1, arr[0] = curent

# 当i=2时，current = arr[2]
#          preIndex = 1,  如果arr[1] > current, arr[2] = arr[1], preIndex=0; 值交换位置
#          preIndex = 0,  如果arr[0] > current, arr[1] = arr[0], preIndex=-1;
# 退出循环,preIndex = -1, arr[0] = current

# 当i=3时，current = arr[3]
#          preIndex = 2,  如果arr[2] > current, arr[3] = arr[2], preIndex=1;
#          preIndex = 1,  如果arr[1] > current, arr[2] = arr[1], preIndex=0;
#          preIndex = 0,  如果arr[1] > current, arr[1] = arr[0], preIndex=-1;
# 退出循环,preIndex = -1, arr[0] = current     

# 注意：current 是传递的中间值；传递是在相邻元素之间交替进行的。

4. 希尔排序 shell sort

希尔排序 是对插入排序的一种优化，插入排序的原理可知，每次只能移动一个位置。 shell sort采用步长分割后再进行排序，本质是分组插入排序。具体实现是， 首先数组长度除以步长(gap)，后续步长再除以gap的缩小值，直到以gap=1为步长排序。

def shell_sort(arr: list) -> list:
    import math 
    # 指定步长的长度
    gap = 1
    while (gap < len(arr)/3):
        gap = gap*3 + 1
        print('gap=',gap)
    # 步长长度随着数组的长度而改变，
    # 但是进入排序之前会是一个定值
    while gap > 0:
        #使用直接的插入排序
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap 
            while j >= 0 and arr[j] > temp:
                arr[j+gap] = arr[j]
                j -= gap 
            arr[j+gap] = temp
        # 减小gap
        gap = math.floor(gap/3)
    return arr