数据结构-排序(一)

发表于 2019-03-10 分类于计算机基础，数据结构阅读次数： Disqus：本文字数： 4.1k 阅读时长 ≈ 4 分钟

数据结构-排序(一),包括 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)$

代码

# 插入排序
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)$

代码

# 选择排序
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,序列有序.
图解
算法复杂度
- 时间复杂度
  - 希尔排序是非稳定排序.
- 空间复杂度
  - 与插入排序相同, $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$

代码

这里是将所有不同步长的插入排序的循环整合到了一起.

# 希尔排序
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,序列排序完成
图解
算法复杂度
- 时间复杂度
  - 对于长度为n的序列,冒泡排序需要 $O(n^2)$ 次比较.
  - 与插入排序相比需要的交换次数更多,插入排序是一次移动到位,冒泡排序每次仅移动一个位置.
- 空间复杂度
  - 原地排序,空间复杂度为 $O(1)$ .
改进
- 一般仅用于理解排序算法,不会在实际的项目中使用冒泡,但还是可以简单的改进以下.
- 冒泡排序只在一个方向上比较,对于长度较小的数组,无效比较过多.
- 在冒泡排序的基础上,增加一个反向排序,选出最小值,对小型数组减少了无效的比较.
- 这样也被成为定向冒泡排序/鸡尾酒排序/涟漪排序

代码

# 冒泡排序
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. 返回左右子序列合并的结果.
图解
算法复杂度
- 时间复杂度
  - 递归写法中,合并的操作,访问序列共n次,所以有如下递归方程
  - $T(n) = T(n/2) + n$
  - 由Master定理可得,时间复杂度为 $O(n\log n)$
- 空间复杂度
  - 需要一个最大长度为n的辅助数组,因此空间复杂度为 $O(n)$
改进
- 与希尔排序类似,对小规模子序列改用插入排序,效果更好.
- 归并排序主体很难更改,改进放在合并上.
  - 合并前比较两输入序列的最大值最小值,如其中一个最大值 < 另一个的最小值,此时可以跳过合并操作,直接连接两个子序列.
  - 降低合并操作的时间复杂度,不可避免的除最大值<最小值的情况外,比较操作还是需要n次,但可以由移动节点入手,降低复杂度.
  - ps: 实际上对合并操作的辅助数组实际上是空间换时间,不考虑合并操作的时间复杂度时,可以做到原地合并,但魔改后,时间复杂度不再是 $O(n)$ ,master定理对归并排序整体时间复杂度的判断不再成立.

代码

# 归并排序
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