算法：排序精讲

Snipaste_2020-04-05_23-55-48.png

所有非比较类排序算法（计数排序、桶排序、基数排序）都是稳定的，比较类排序算法中，除了冒泡排序、简单插入、归并排序这三种算法是稳定的，其他算法都是不稳定的。

参考链接

本文内容整理自以下几篇博客： 十大经典排序算法（动图演示） 十大经典排序算法动画，看我就够了！ 视频 | 手撕九大经典排序算法，看我就够了！ 排序算法（九）：桶排序

排序算法分类

Snipaste_2020-04-05_23-55-48.png

算法稳定性

所谓稳定性，是指在排序的过程中，元素原来的相对次序是否变化，稳定的排序算法不会改变原始的相对次序，而不稳定的排序算法则会改变这个次序。

Snipaste_2020-04-10_22-01-37.png
算法名称 稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
冒泡排序 稳定 \(O(n^2)\) \(O(n^2)\) \(O(n)\) \(O(1)\)
快速排序 不稳定 \(O(nlog_2n)\) \(O(n^2)\) \(O(nlog_2n)\) \(O(nlog_2n)\)
简单插入排序 稳定 \(O(n^2)\) \(n(n^2)\) \(O(n)\) \(O(1)\)
希尔排序 不稳定 \(O(n^{\frac{3}{2}})\) \(O(n^2)\) \(O(n)\) \(O(1)\)
简单选择排序 不稳定 \(O(n^2)\) \(n(n^2)\) \(O(n^2)\) \(O(1)\)
堆排序 不稳定 \(O(nlog_2n)\) \(n(nlog_2n)\) \(O(nlog_2n)\) \(O(1)\)
二路归并排序 稳定 \(O(nlog_2n)\) \(O(nlog_2n)\) \(O(nlog_2n)\) \(O(n)\)
计数排序 稳定 \(O(n + k)\) \(O(n + k)\) \(O(n + k)\) \(O(n + k)\)
桶排序 稳定 \(O(n+k)\) \(n(n^2)\) \(O(n)\) \(O(n+k)\)
基数排序 稳定 \(O(n \times k)\) \(O(n \times k)\) \(O(n \times k)\) \(O(n + k)\)

下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是（C）。 A．直接插入排序 B．冒泡排序 C．直接选择排序 D．快速排序

下列排序算法中时间复杂度不受数据初始状态影响，恒为 O(\(n^2\)) 的是（C） A. 堆排序 B. 冒泡排序 C. 直接选择排序 D. 快速排序

外部排序和内部排序

  • 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
  • 内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。

比较类排序

通过元素比较来决定相对次序，时间复杂度不能突破 \(O(nlogn)\)，又称非线性时间比较类排序。

交换排序

冒泡排序（Bubble Sort）

算法思想

重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换的元素，也就是说该数列已经排序完成。

  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，每次都从第0个元素开始两两交换，第 n 次交换到第 len(nums)-1-n 个元素，0<n<len(nums)-1；
  • 重复步骤1~3，直到排序完成。

图示

v2-33a947c71ad62b254cab62e5364d2813_b.gif

Python实现

1
2
3
4
5
6
7
8
9
10
def bubbleSort(nums):
    tmp = None
    _len = len(nums)
    for i in range(_len):
        for j in range(0, _len-1-i):  # 进行了 j+1 的比较，所以为了防止越界，这里要减1。
            if nums[j] > nums[j+1]:  # 出现降序
                tmp = nums[j+1]
                nums[j+1] = nums[j]
                nums[j] = tmp
    return nums

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
稳定 \(O(n^2)\) \(O(n^2)\) \(O(n)\) \(O(1)\)

快速排序（Quick Sort）

算法思想

基于分治的思想

  • 先从数列中取出一个数作为key值；
  • 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
  • 递归的对左右两个小数列重复第二步，直至各区间只有1个数。

图示

Python实现

  • 推荐方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def quickSort(nums, left, right):
    if left >= right:
        return
    i, j, key = left, right, nums[left]  # 选择第一个数为key
    while i < j:
        # 从右向左找第一个小于等于key的值
        while i < j and nums[j] >= key:
            j -= 1
        # 从左向右找第一个大于key的值
        while i < j and nums[i] <= key:
            i += 1
        # 找到了小于等于key的就扔到前面, 找到大于等于key的就扔到后面
        nums[j], nums[i] = nums[i], nums[j]
    
    # 更新left和i
    nums[i], nums[left] = nums[left], nums[i]
    # 递归调用
    self.quickSort(nums, left, i-1)
    self.quickSort(nums, i+1, right)

    return nums  # 原地算法/非原地算法皆可以
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quickSort(nums, left, right):
    if left >= right:
        return
    i, j, key = left, right, nums[left]  # 选择第一个数为key
    while i < j:
        while i < j and nums[j] >= key:  # 从右向左找第一个小于等于key的值
            j -= 1
        if i < j:  # 找到了小于等于key的就扔到前面
            nums[i] = nums[j]
            i += 1

        while i < j and nums[i] <= key:  # 从左向右找第一个大于key的值
            i += 1
        if i < j:  # 找到大于等于key的就扔到后面
            nums[j] = nums[i]
            j -= 1
        
    nums[i] = key
    quickSort(nums, left, i-1)
    quickSort(nums, i+1, right)
    
    return nums # 可以原地算法/也可以非原地算法

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
不稳定 \(O(nlog_2n)\) \(O(n^2)\) \(O(nlog_2n)\) \(O(nlog_2n)\)

插入排序

简单插入排序（Insertion Sort）

算法思想

将无序部分中的元素插入到有序部分。初始化时，从第一个元素开始，依次搜索每一个元素的待插入位置，算法中，有序部分在前，无序部分在后，一边寻找插入位置，一边将元素后移一个单元。一直在往前找适和当前元素的位置。

图示

Python实现

1
2
3
4
5
6
7
8
9
10
11
def insertSort(nums):
    i = 1
    length = len(nums)
    for i in range(1, length):  # 由于是向前搜索，所以i从1开始，预留一个0位置。
        tmp = nums[i]  # 图中的红色框
        j = i  # j是往前搜索时的指示下标，从i开始，最终停在要插入的位置。
        while j > 0 and tmp < nums[j-1]:  # j一直往前搜索，直到j减小到0。
            nums[j] = nums[j-1]  # 将元素后移一个单元。
            j -= 1
        nums[j] = tmp  # 将元素插入到搜索到的位置
    return nums

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
稳定 \(O(n^2)\) \(n(n^2)\) \(O(n)\) \(O(1)\)

希尔排序（Shell Sort）

算法思想

简单插入排序的修改版，根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。1959年Shell发明，第一个突破 \(O(n^2)\) 的排序算法，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

图示

v2-c52e08027910d98f78ee1d225cf03a8b_720w.jpg

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def shellSort(nums):
    # 这里和图片演示的不一样，图片是分组执行简单插入排序的，实际操作是多个分组交替执行。
    n = len(nums)
    gap = n // 2
    while gap > 0:
        i = gap  # 由于简单插入排序是向前搜索的，所以这里设置i=gap，然后i-=gap，而非i=0，i+=gap。
        while i < n:  # 等效于 for i in range(gap, n)
            tmp = nums[i]  # 待插入元素 
            j = i  # j是往前搜索时的指示下标，j每次减小gap，从i开始，最终停在要插入的位置。
            while j >= gap and tmp < nums[j-gap]:  # j一直往前搜索，直到j减小到0。
                nums[j] = nums[j-gap]  # 将元素后移一个gap。
                j -= gap
            nums[j] = tmp  # 将元素插入到搜索到的位置
            i += 1
        gap = gap // 2  # gap（增量）减小
    return nums

时空复杂度和稳定性

希尔排序的平均时间复杂度和步长序列有之间关系

稳定性 步长序列 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
不稳定 \(2^i3^j\) \(O(nlog^2n)\) \(O(n)\) \(O(n)\)
\(2^k-1\) \(O(n^{\frac{3}{2}})\) \(O(n)\) \(O(n)\)
\(\frac{n}{2^i}\) \(O(n^2)\) \(O(n)\) \(O(n)\)

选择排序

简单选择排序（Selection Sort）

算法思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始（末尾）位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的末尾。以此类推，直到所有元素均排序完毕。注意，这里有个有序区和无序区的概念。

图示

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def selectSort(nums):
    _len = len(nums)
    end = _len - 1  # end之后就是有序区
    while end > 0:
        index = 0
        for i in range(1, end + 1):  # 在无序区中找最大值
            _max = nums[index]
            if nums[i] > _max:
                index = i
        # 交换
        tmp = nums[end]
        nums[end] = nums[index]
        nums[index] = tmp
        # 扩大有序区
        end -= 1

    return nums

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
不稳定 \(O(n^2)\) \(n(n^2)\) \(O(n^2)\) \(O(1)\)

堆排序（Heap Sort）

算法思想

堆排序是一种基于二叉堆（Binary Heap）结构的排序算法，所谓二叉堆，就是一种特殊的完全二叉树，只不过相比较完全二叉树而言，二叉堆的所有父节点的值都大于（或者小于）它的孩子节点，像这样：

v2-5d6119c9801eadb83402ef68f6d4b689_720w.jpg

首先需要引入最大堆（大根堆）的定义：

  • 最大堆中的最大元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都大于等于其孩子结点

类似的，还有最小堆（小根堆）：

  • 最大堆中的最小元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都小于等于其孩子结点
650075-91f1549ff0c87c15.png

那么，堆排序算法的内容就很简单了，最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。

图示

Python实现

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
35
36
def heapSort(nums):
    # 交换
    def swap(nums, i, j):
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp

    # 调整堆
    def heapify(nums, n, i):  # nums是数组、n是要调整的区间长度，i是要调整的根节点下标。
        largest = i
        l = 2 * i + 1  # 左节点
        r = 2 * i + 2  # 右节点
        if l < n and nums[l] > nums[largest]:  # 如果 left 比 root 大的话，l<n用于控制调整区间。
            largest = l
        if r < n and nums[r] > nums[largest]:  # 如果 right 比 root 大的话，r<n用于控制调整区间。
            largest = r
        if largest != i:  # 说明进行了调整，将堆顶和调整目标进行交换
            swap(nums, i, largest)
            # 递归调整子节点，此时largest是left或者right的节点的下标。
            heapify(nums, n, largest)

    n = len(nums)

    # 建立堆
    #  range(n//2-1, -1, -1)是所有非叶子节点。从最后一个非叶子节点开始，使用heapify函数调整，保证根节点数值大于叶子节点数值。
    for i in range(n // 2 - 1, -1, -1):  # i就是一个非叶子节点
        heapify(nums, n, i)

    # 调整完之后，就建立了一个大根堆，从堆顶（nums[0]）取出元素。
    for i in range(n-1, -1, -1):  # i用于标记有序区，nums[>i]的部分都是有序区。
        # 一个一个的从堆顶（nums[0]）取出元素，和list无序区最后的元素nums[i]交换。
        swap(nums, i, 0)
        # 交换完成之后，从堆顶往下调整，使用i控制调整不会影响有序区。
        heapify(nums, i, 0)

    return nums

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
不稳定 \(O(nlog_2n)\) \(n(nlog_2n)\) \(O(nlog_2n)\) \(O(1)\)

归并排序

二路归并排序（Merge Sort）

算法思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）思想。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。若将K个有序表合并成一个有序表，称为多路归并排序。

  • 如果给的数组只有一个元素的话，直接返回（也就是递归到最底层的情况）
  • 把整个数组分为尽可能相等的两个部分（分）
  • 对于两个被分开的两个部分进行整个归并排序（治）
  • 把两个被分开且排好序的数组拼接在一起

图示

v2-6639ef7ed441b0e2b7a71ee202e3ad05_720w.jpg

Python实现

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
def mergeSort(nums):
    def merge(left, right):
        result = []
        # 开始合并
        while len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        # 如果left还有的剩，就放入left。
        while len(left):
            result.append(left.pop(0))

        # 如果right还有的剩，就放入right
        while len(right):
            result.append(right.pop(0))
        
        return result

    _len = len(nums)
    if _len < 2:
        return nums
    
    mid = _len // 2
    # 分开
    left = nums[:mid]
    right = nums[mid:]
    # 合并
    return merge(mergeSort(left), mergeSort(right))

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
稳定 \(O(nlog_2n)\) \(O(nlog_2n)\) \(O(nlog_2n)\) \(O(n)\)

非比较类排序

不通过比较来决定元素间的相对次序，时间复杂度可以达到 \(O(n)\)，又称线性时间非比较类排序。

计数排序（Counting Sort）

算法思想

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。条件苛刻，且牺牲空间换取时间。

图示

Python实现

1
2
3
4
5
6
7
8
9
def countSort(nums, start, end):
    counter = [0 for _ in range(start, end+1)]
    for i in nums: counter[i-start] += 1
    cur = 0  # 设置一个cur来控制填充
    for i in range(end-start+1):  # 注意循环从0开始一直到区间结束end-start+1
        for _ in range(counter[i]):
            nums[cur] = i + start
            cur += 1
    return nums

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
稳定 \(O(n + k)\) \(O(n + k)\) \(O(n + k)\) \(O(n + k)\)

\(n\) 是待排序元素个数，\(k\) 是待排序元素区间长度。

桶排序（Bucket sort）

算法思想

桶排序是计数排序的升级版，桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

桶排序过程中存在两个关键环节： 1、元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择。 2、排序算法的选择，从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。

算法过程：

  • 设置一个定量的数组当作空桶；
  • 遍历输入数据，并且把数据一个一个放到对应的桶里去；
  • 对每个不是空的桶进行排序；
  • 从不是空的桶里把排好序的数据拼接起来。

图示

v2-58b4d4b9e802104727677d7b0b60157a_b.gif

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def bucketSort(nums):
    _max, _min = max(nums), min(nums)
    # 设置映射关系，每10个数为一个桶。
    bucket = [[] for _ in range(_max // 10 - _min // 10 + 1)]
    # 将数映射到桶里面
    for i in nums:
        index = i // 10 - _min // 10  # 映射过程就是用数字计算桶的索引
        bucket[index].append(i)
    # nums.clear()
    nums = []
    # 对桶中的数字进行排序再拼接
    for i in bucket:
        i.sort()
        # nums.extend(i)
        nums += i

    return nums

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
稳定 \(O(n+k)\) \(n(n^2)\) \(O(n)\) \(O(n+k)\)

\(n\) 是待排序元素个数，\(k\) 是待排序元素区间长度。

基数排序（Radix Sort）

算法思想

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

  • 取得数组中的最大数，并取得位数；
  • nums 为原始数组，从最低位开始取每个位组成 radix 数组；
  • 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

图示

v2-3a6f1e5059386523ed941f0d6c3a136e_b.gif

Python实现

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
def radixSort(nums):
    _len = len(nums)
    counter = [[] for _ in range(10)]  # 十进制基数只有0-9十种，所以counter是一个长度为10的list
    mod = 10  # 注意这个变量 mod是从10开始的
    dev = 1  # dev是从1开始的
    i = 0
    maxDigit = 0 
    _max = max(nums)
    # 计算最大值的位数
    while _max:
        _max //= 10
        maxDigit += 1

    # 从以第一位为基准，一直遍历到以最高位为基准，进行排序。
    while i < maxDigit:
        for j in range(_len):
            radix = int((nums[j] % mod) // dev)  # 计算当前位上面的数字，先取余，再除以dev求解当前位上面的数字。
            counter[radix].append(nums[j])
        pos = 0
        for j in range(len(counter)):
            if len(counter[j]):
                while len(counter[j]):
                    value = counter[j].pop(0)
                    nums[pos] = value
                    pos += 1
        i += 1
        dev *= 10
        mod *= 10

    return nums

时空复杂度和稳定性

稳定性 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
稳定 \(O(n \times k)\) \(O(n \times k)\) \(O(n \times k)\) \(O(n + k)\)

其中 \(n\) 是排序元素个数，\(k\) 是数字位数。

Python有点意思

两个 Python list 的内建函数

1
2
3
4
5
6
7
# 清空list
nums.clear()
nums = []

# 拓展list
nums.extend(new_numes)
nums += new_numes

i

算法与数据结构
排序算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！