数据结构-排序(一)

  • 数据结构-排序(一),包括 python 源代码

  • 更新

    1
    19.03.08 初始
  • 参考资料

    https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000
    维基百科
    算法第四版,算法导论.

导语

  • 排序部分重构比较容易,但是算法的证明,复杂性分析等较多.分为两节.
  • 堆排序,快速排序等放在下一节.
  • 计数排序/基数排序/桶排序,准备放到遥远的第三节.
  • 排序的动画图片均取自维基百科.
  • 简单排序代码来自维基百科.

排序

  • 本章约定,所涉及序列取值为正整数.

  • 排序算法: 将一串资料依照特定排序方式进行排列的算法.最常见的递增/递减序列.

  • 依照排序的方式不同有以下的简单分类.

    • 比较类
      • 插入
        • 插入排序
        • 希尔排序
      • 交换
        • 选择排序
        • 冒泡排序
        • 快速排序
      • 选择
        • 堆排序
      • 归并
        • 归并排序
    • 非比较排序
      • 关键值本身就含有了定位特征,不需要比较就可以确定其前后位置.
      • 计数排序/基数排序/桶排序等.(遥遥无期的第3节)
  • 算法复杂度

    • 时间复杂度
      • 一个排序算法通常需要计量 最差/平均/最好性能.
      • 一般时间复杂度都是与输入的序列长度 n 成正比.
      • 一般而言 好的性能是 $O(n\log {n})$ .而最差性能是 $O(n^2)$.最理想的性能是 $O(n)$ (但平均而言不可能达到).基于比较的排序算法时间复杂度一般会大于等于 $O(n\log {n})$.
      • 计量时间成本,这里选择比较和交换的数量,对于不交换元素的数组,选择访问数组的次数.
    • 空间复杂度
      • 各个算法的空间复杂度相差较大.
      • 即使同一个排序算法,不同的实现方法也千差万别.

插入排序

  • 步骤:

    1. 由第一个元素开始,认为已经被排序.
    2. 取出下一个元素插入左边已有序序列.
    3. 重复 12 直到序列完全有序.
  • 步骤2时,一般有两种方式.

    • 由后向前扫描,直到找到新元素的位置插入.
    • 二分查找,直到找到新元素位置.(二分插入排序)
  • 图解

    • 插入排序
  • 算法复杂度

    • 时间复杂度
      • 最好情况: 输入序列有序.此时需要比较 $(n-1)$ 次.时间复杂度 $O(n)$
      • 最坏情况: 输入序列逆序,此时需要比较 $\frac {1}{2}n(n-1)$ 次,时间复杂度为 $O(n^2)$
      • 平均情况: 时间复杂度为 $O(n^2)$(证明看不懂)
    • 空间复杂度
      • 仅用一个辅助位置,空间复杂度为 $O(1)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # 插入排序
    def InsertSort(self, arr):
    for i in range(1, len(arr)):
    temp = arr[i]
    j = i - 1
    # 由后向前扫描
    while j >= 0 and temp < arr[j]:
    arr[j + 1] = arr[j]
    j -= 1
    arr[j + 1] = temp
    return arr

选择排序

  • 步骤

    1. 从第一个元素开始,认为第一个元素已排列,为有序序列.
    2. 找到未排序序列中最小的元素.
    3. 与未排序的序列第一个元素交换位置.
    4. 重复 23 直到未排序序列消失,序列有序.
  • 图解

    • 选择排序
  • 算法复杂度

    • 时间复杂度
      • 运行时间与输入序列的初始状态无关,输入一个长度相等的有序序列/逆序序列,两者的比较操作一样多.
      • 算法复杂度为 $O(n^2)$
    • 空间复杂度
      • 原地排序,不需要辅助空间.空间复杂度$O(1)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 选择排序
    def selectionsort(self, arr):
    for i in range(len(arr)):
    minindex = i
    # 选择未排序序列最小值
    for j in range(i + 1, len(arr)):
    if arr[minindex] > arr[j]:
    minindex = j
    if i == minindex:
    pass
    else:
    arr[i], arr[minindex] = arr[minindex], arr[i]
    return arr

希尔排序

  • 希尔排序是插入排序的重要改进版.插入排序效率低下,和每次只将数据移动一位有关.希尔排序基于如下思想: 如果一个序列有序,则间隔(步长)为 n 的子序列也是有序的.逐渐将间隔(步长) n 缩短到1时,整个序列有序.

  • 步骤

    1. 选取间隔 n 值.
    2. 对序列进行间隔为 n 的子序列进行插入排序
    3. 重复1 2,直到 n = 1,序列有序.
  • 图解

    • shellsort
  • 算法复杂度

    • 时间复杂度
      • 希尔排序是非稳定排序.
    • 空间复杂度
      • 与插入排序相同, $O(1)$
  • 改进

    • 希尔排序通过排列间隔n的子序列,来一次将数据移动n个长度,n的取值对希尔排序的效率至关重要.
    • 开始时希尔排序采用步长 n 取值为 $\frac2n$,这样比插入排序 $O(n^2)$ 要好,但依旧存在改进空间.
    • 希尔排序目前最好的步长序列为 $(1,5,19,109)$ 来自 $9\times 4^i - 9\times 2^i + 1$,整个步长序列在小数组的速度要比堆排序和快速排序都要好,但大数组时还是比快速排序慢.
    • 直观上步长 n 的选择,需要满足小步长的n值排序后,不会影响大步长n值的排序结构.
    • ps: 在n值非常小时,可以直接使用冒泡/插入排序,节省时间.
  • 应用

    • 希尔排序代码量很小,不需要额外的内存空间,在没有系统排序函数/嵌入式系统中首选,性能优化阶段再考虑其他排序算法.
    • 一个常用的步长序列: $n = 3 \times n + 1$
  • 代码

    • 这里是将所有不同步长的插入排序的循环整合到了一起.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    # 希尔排序
    def ShellSort(self, arr):
    n = len(arr)
    # 初始步长
    gap = n // 2
    while gap > 0:
    for i in range(gap, n):
    # 每个步长进行插入排序
    temp = arr[i]
    j = i
    # 插入排序
    while j >= gap and arr[j - gap] > temp:
    arr[j] = arr[j - gap]
    j -= gap
    arr[j] = temp
    # 得到新的步长
    gap = gap // 2
    return arr

冒泡排序

  • 步骤

    1. 从头扫描序列,第一个元素大于第二个元素,即交换位置.
    2. 重复比较相邻元素,直到未排列的序列末尾,末尾元素即未排列序列的最大值,最大值已排序.
    3. 重复 1 2 直到未排序序列长度为1,序列排序完成
  • 图解

    • Bubble Sort
  • 算法复杂度

    • 时间复杂度
      • 对于长度为n的序列,冒泡排序需要 $O(n^2)$ 次比较.
      • 与插入排序相比需要的交换次数更多,插入排序是一次移动到位,冒泡排序每次仅移动一个位置.
    • 空间复杂度
      • 原地排序,空间复杂度为 $O(1)$ .
  • 改进

    • 一般仅用于理解排序算法,不会在实际的项目中使用冒泡,但还是可以简单的改进以下.
    • 冒泡排序只在一个方向上比较,对于长度较小的数组,无效比较过多.
    • 在冒泡排序的基础上,增加一个反向排序,选出最小值,对小型数组减少了无效的比较.
    • cocktail_sort
    • 这样也被成为定向冒泡排序/鸡尾酒排序/涟漪排序
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    # 冒泡排序
    def BubbleSort(self, arr):
    list_len = len(arr)
    for i in range(list_len - 1):
    for j in range(list_len - 1, i, -1):
    if arr[j] < arr[j - 1]:
    arr[j], arr[j - 1] = arr[j - 1], arr[j]
    return arr

归并排序

  • 归并排序是典型的分治法思想,对分治法的详细分析会在,算法-分治法中进行.

  • 归并排序有两种写法,这里仅提及递归写法.

  • 步骤

    • 合并
      • 比较两个序列末尾元素,依照由大到小合并两个已有序的序列,
    • 归并
      1. 序列长度 = 1,返回序列.
      2. 将输入序列1分为2
      3. 对左子序列进行归并排序
      4. 对右子序列进行归并排序
      5. 返回左右子序列合并的结果.
  • 图解

    • mergesort
  • 算法复杂度

    • 时间复杂度
      • 递归写法中,合并的操作,访问序列共n次,所以有如下递归方程
      • $$T(n) = T(n/2) + n$$
      • 由Master定理可得,时间复杂度为 $O(n\log n)$
    • 空间复杂度
      • 需要一个最大长度为n的辅助数组,因此空间复杂度为 $O(n)$
  • 改进

    • 与希尔排序类似,对小规模子序列改用插入排序,效果更好.
    • 归并排序主体很难更改,改进放在合并上.
      • 合并前比较两输入序列的最大值最小值,如其中一个最大值 < 另一个的最小值,此时可以跳过合并操作,直接连接两个子序列.
      • 降低合并操作的时间复杂度,不可避免的除最大值<最小值的情况外,比较操作还是需要n次,但可以由移动节点入手,降低复杂度.
      • ps: 实际上对合并操作的辅助数组实际上是空间换时间,不考虑合并操作的时间复杂度时,可以做到原地合并,但魔改后,时间复杂度不再是 $O(n)$ ,master定理对归并排序整体时间复杂度的判断不再成立.
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    # 归并排序
    def MergeSort(self, arr):
    # 序列长度为1
    if len(arr) <= 1:
    return arr
    # 取中间值
    mid = len(arr) // 2
    # 递归调用
    left = self.MergeSort(arr[:mid])
    right = self.MergeSort(arr[mid:])
    # 归并
    return self.merge(left, right)
    # 合并
    def merge(self, left, right):
    # 最大值小于最小值,跳过合并
    if left[0] >= right[-1]:
    result = right + left
    elif left[-1] <= right[0]:
    result = left + right
    else:
    # 正常合并过程
    result = []
    # 取元素直到某个序列为空
    while left and right:
    if left[0] <= right[0]:
    result.append(left.pop(0))
    else:
    result.append(right.pop(0))
    # 合并剩余不为空的序列
    if left:
    result += left
    if right:
    result += right
    return result