Sui Xin's Blog

十大排序算法

Posted on In Disqus:

1. 冒泡排序

时间复杂度：$O(n^2)$
稳定性：稳定

算法描述

  1. 从头到尾比较相邻两个元素，如果第一个比第二个大，则交换位置；
  2. 依次往后，直到最后一对，这样在数组末尾应该是当前最大值；
  3. 除了后面已经排好的序列重复上面的步骤，直到排序结束。

特点

比较适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。
在数据完全有序的时候展现出最优时间复杂度，为$O(n)$，其他情况下，几乎总是$O(n^2)$。

动图演示

代码

1
2
3
4
5
6
def bubbleSort(array):
    for i in range(len(array)):
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

代码优化：增加一个swap标志，若一次循环中没有任何值交换位置，则说明排序已经完成，跳出即可。

1
2
3
4
5
6
7
8
9
10
def bubbleSort2(array):
    for i in range(len(array)):
        swap = False
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                swap = True
        if not swap:
            break
    return array

2. 选择排序

时间复杂度：$O(n^2)$
稳定性：不稳定

算法描述

  1. 在未排序的序列中找出最小的元素，存放到数组的开始位置；
  2. 重复上述操作，直到排序结束。

特点

在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。
但是，由于固有的$O(n^2)$复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。

动图演示

代码

1
2
3
4
5
6
7
8
def selectSort(array):
    for i in range(len(array) - 1):
        min_idx = i
        for j in range(i + 1, len(array)):
            if array[j] < array[min_idx]:
                min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i]
    return array

3. 插入排序

时间复杂度：$O(n^2)$
稳定性：稳定

算法描述

  1. 将序列分为已排序和未排序两段，每次将未排序的第一个元素插入前面已排序的正确位置；
  2. 重复上述操作，直到排序结束

特点

插入排序由于$O(n^2)$的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。

动图演示

代码

1
2
3
4
5
6
7
8
def insertionSort(array):
    for i in range(len(array) - 1):
        cur, pre_idx = array[i + 1], i
        while pre_idx >= 0 and cur < array[pre_idx]:
            array[pre_idx + 1] = array[pre_idx]
            pre_idx -= 1
        array[pre_idx + 1] = cur
    return array

4. 希尔排序

时间复杂度：$O(n\log n)$
稳定性：不稳定

算法描述

  1. 设置一个增量序列，最后一个为1；
  2. 分别将序列按照第一个增量分为若干字列，对每个子列进行插入排序；
  3. 对下一个增量做同样的插入排序，直到为1时排序结束。

例子：对于待排序列 {44，12，59，36，62，43，94，7，35，52，85}，我们可设定增量序列为 {5，3，1}。

特点

希尔排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀——快速排序$O(n\log n)$快。在大量数据面前，希尔排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。

代码

本代码中动态定义间隔序列的算法是《算法（第4版》的合著者 Robert Sedgewick 提出的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def shellSort(array):
    length = len(array)
    gap = 1
    while gap < length // 3:
        gap = gap * 3 + 1
    while gap > 0:
        for i in range(gap, length):
            cur, pre_idx = array[i], i - gap
            while pre_idx >= 0 and cur < array[pre_idx]:
                array[pre_idx + gap] = array[pre_idx]
                pre_idx -= gap
            array[pre_idx + gap] = cur
        gap //= 3
    return array

5. 归并排序

时间复杂度：$O(n\log n)$
稳定性：稳定

算法描述

采用分治法的思想，将原始序列分为两段，两段分别归并排序后，再合并。合并时将两个已排序序列的首部开始比较，总是将小的那个加入到结果中，如果有一个序列已经遍历结束，则将另一个序列剩余的部分直接添加进来。

特点

归并排序在数据量比较大的时候也有较为出色的表现，但是，其空间复杂度$O(n)
$使得在数据量特别大的时候几乎不可接受。考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。

动图演示

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def mergeSort(array):
    def merge(left, right):
        res = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1
        return res + left[i:] + right[j:]
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left, right = mergeSort(array[:mid]), mergeSort(array[mid:])
    return merge(left, right)

6. 快速排序

时间复杂度：$O(n\log n)$
稳定性：不稳定

算法描述

  1. 对于当前的区间 [left, right] 进行快排：
    1. 将当前区间的第一个元素令为 key，称为“基准”(pivot)；
    2. 使用双指针比较所有剩余的元素，小于 pivot 的放到左边，大于 pivot 的放到右边。
  2. 对放到左右两部分再进行快排保持有序。

特点

快速排序是原地排序，不占用额外空间。快速排序尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑优化以提高其在最坏情况下的性能。

动图演示

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quick_sort(array, left=None, right=None):
    if left is None or right is None:
        left, right = 0, len(array) - 1
    if left >= right:
        return
    low, high = left, right
    key = array[left]
    while left < right:
        while left < right and array[right] >= key:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] <= key:
            left += 1
        array[right] = array[left]
    array[left] = key
    quick_sort(array, low, left)
    quick_sort(array, left + 1, high)

7. 堆排序

时间复杂度：$O(n\log n)$
稳定性：不稳定

堆

堆是一种特殊的完全二叉树，二叉堆一般分为两种：
最大堆：每个父节点的值都大于或等于其子节点的值（若存在）
最小堆：每个父节点的值都小于或等于其子节点的值（若存在）

算法描述

堆排序的原理就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。
调整最大堆：对于一个指定不满足最大堆条件的结点进行“下沉”使其满足最大堆条件；
建立最大堆：从一个堆的最后一个非叶子结点开始进行调整，往前再调整前一个非叶子结点……
堆排序：创建最大堆——取出最大堆堆顶元素与堆尾元素互换位置（为了节省存储空间）——对堆顶元素进行调整最大堆——取出堆顶元素——……

特点

堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。

代码

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
def heapSort(array):
    def adjustHeap(arr, idx, size):
        """调整二叉堆为最大堆
        idx: 当前结点需要调整
        size: 二叉堆的大小（后面的不用调整，因为用来存放排好序的结果）"""
        lchild = 2 * idx + 1
        rchild = 2 * idx + 2
        largest = idx
        if lchild < size and arr[lchild] > arr[largest]:
            largest = lchild
        if rchild < size and arr[rchild] > arr[largest]:
            largest = rchild
        if largest != idx:
            arr[largest], arr[idx] = arr[idx], arr[largest]
            adjustHeap(arr, largest, size)

    def buildHeap(arr, size):
        # 从最后一个非叶子结点开始建立
        for i in range(size // 2)[::-1]:
            adjustHeap(arr, i, size)

    size = len(array)
    buildHeap(array, size)
    for i in range(size)[::-1]:
        array[0], array[i] = array[i], array[0]  # 将最大堆顶元素放入后面，节省了存储空间
        adjustHeap(array, 0, i)
    return array

8. 计数排序

时间复杂度：$O(n+k)$，其中$k$为$max(array) - min(array) + 1$
稳定性：稳定

算法描述

  1. 将原始数组映射到count范围为$[0, N+1]$中，每个位置存放不大于该数字的数字出现的次数；
  2. 若不大于$i$的数有$s$个（包括了$i$本身），那么$i$应该放在$s - 1$的位置上。

特点

排序目标要能够映射到整数域，其最大值最小值应当容易辨别。另外，计数排序需要占用大量空间，它比较适用于数据比较集中的情况。

动图演示

代码

1
2
3
4
5
6
7
8
9
10
11
12
def countSort(array):
    min_num = min(array)
    count = [0] * (max(array) - min_num + 1)  # 将原始[min, max]映射到[0, N+1]
    res = [0] * len(array)
    for i in array:
        count[i - min_num] += 1  # 将数i减去最小值即为正确位置
    for i in range(1, len(count)):
        count[i] += count[i - 1]  # count中i位置变为array中不大于i的数量
    for i in array:
        res[count[i - min_num] - 1] = i  # 因为不大于i的数有count[i - min_num]个，所以i应该放在count[i - min_num] - 1的位置上
        count[i - min_num] -= 1  # 放好一个数，就将对应的位置数量-1
    return res

9. 桶排序

算法描述

桶排序又叫箱排序，是计数排序的升级版，它的工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

  1. 找出数组的最大值max_num和最小值min_num；
  2. 桶的数量设置为(max_num - min_num) // length + 1；
  3. 将数组按照桶的个数等分，然后把每个元素放入对应的桶；
  4. 对每个桶内元素进行排序；
  5. 将所有的桶拼接起来。

特点

在分桶和从桶依次输出的过程是稳定的，但桶排序的稳定性还依赖于桶内的排序算法。桶排序可用于最大最小值相差较大的数据情况，但桶排序要求数据的分布尽量均匀，否则可能导致数据都集中到一个桶中。

图片示意

代码

1
2
3
4
5
6
7
8
9
10
11
12
def bucketSort(array):
    min_num, max_num, length = min(array), max(array), len(array)
    num_bucket = (max_num - min_num) // length + 1
    buckets = []  # 此处不能直接使用buckets = [[]] * num_bucket，会导致内存地址指向同一处
    for _ in range(num_bucket):
        buckets.append([])
    for i in array:
        buckets[(i - min_num) // length].append(i)
    array.clear()
    for i in buckets:
        array.extend(quickSort(i))
    return array

10. 基数排序

算法描述

基数排序是桶排序的扩展，主要思想为将非负整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序有两种：

  1. LSD（Least significant digital，次位优先法）：从低位开始进行排序
  2. MSD（Most significant digital，主位优先法）：从高位开始进行排序

特点

基数排序要求较高，排序元素必须是非负整数。

动图演示

代码

该代码只支持非负整数的基数排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def radixSort(array):
    # LSD实现基数排序
    div = 1
    max_length = len(str(max(array)))
    buckets = [[] for _ in range(10)]
    for _ in range(max_length):
        for i in array:
            buckets[i // div % 10].append(i)
        i = 0
        for bucket in buckets:
            while bucket:
                array[i] = bucket.pop(0)
                i += 1
        div *= 10
    return array

复杂度及稳定性

参考

https://www.weiweiblog.cn/10sort/
https://www.jianshu.com/p/bbbab7fa77a2

Related Posts