排序算法

十大经典排序算法_动图演示

常见的10种排序算法

十大经典排序算法动画，看我就够了

十大经典排序算法

分类

十种常见排序算法可以分为两大类：

  • 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(n)$，因此也称为非线性时间比较类排序
  • 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

排序算法

  • 比较类
    • 交换排序
      • 冒泡排序(稳定)
      • 快速排序[分治]
    • 插入排序
      • 简单插入排序(稳定)[打扑克]
      • 希尔排序(插入排序的改进)
    • 选择排序
      • 简单选择排序[选最值]
      • 堆排序
    • 归并排序(稳定)[递归]
      • 二路归并排序
      • 多路归并排序
  • 非比较类
    • 计数排序(稳定)
    • 桶排序(稳定)
    • 基数排序(稳定)

算法复杂度

排序方法 时间复杂度(均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 本地排序
插入排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定 都可
希尔排序 $O(n^{1.3})$ $O(n^2)$ $O(n)$ $O(1)$ 不稳定 都可
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定 都可
堆排序 $O(n log_2n)$ $O(n log_2n)$ $O(n log_2n)$ $O(1)$ 不稳定 都可
冒泡排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定 都可
快速排序 $O(n log_2n)$ $O(n^2)$ $O(n log_2n)$ $O(n log_2n)$ 不稳定 仅本地
归并排序 $O(n log_2n)$ $O(n log_2n)$ $O(n log_2n)$ $O(n)$ 稳定 不支持
计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(n+k)$ 稳定 都可
桶排序 $O(n+k)$ $O(n^2)$ $O(n)$ $O(n+k)$ 稳定 都可
基数排序 $O(n*k)$ $O(n*k)$ $O(n*k)$ $O(n+k)$ 稳定 都可

小结

稳定性记忆方法——快希选堆不稳定

需要使用额外空间的四种排序——基数、计数、桶排、归并

常用时间复杂度大小关系

基本概念

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变

即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的

比较类

冒泡排序(Bubble Sort)

算法描述

  1. 比较相邻的元素: 如果第一个比第二个大，就交换它们两个
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
  3. 针对所有的元素重复以上的步骤，除了最后一个
  4. 重复步骤1~3，直到排序完成

动图演示

代码实现

1
2
3
4
5
6
def bubbleSort(arr):
    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

改进与变种

鸡尾酒排序(Cocktail Sort)

冒泡排序的变形版，也称搅拌排序

  1. 每一轮排序有两个内循环，每轮结束时同时排好了最大和最小两个元素
  2. 第一个循环负责把当前最大值冒泡到最右
  3. 第二个循环把当前最小值冒泡到最左
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def MySort(self, arr):
        n = len(arr)
        
        for i in range(n-1, -1, -1):
            for j in range(1, i+1):
                if arr[j] < arr[j-1]:
                    arr[j], arr[j-1] = arr[j-1], arr[j]

            for j in range(i-1, 0, -1):
                if arr[j] < arr[j-1]:
                    arr[j], arr[j-1] = arr[j-1], arr[j]

        return arr

选择排序(Selection Sort)

工作原理：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果，具体算法描述如下：

  1. 初始状态：无序区为R[1..n]，有序区为空

  2. 第i趟排序(i=1, 2, 3 … n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n)

    该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换

    使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区

  3. n-1趟结束，数组有序化了

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

动图演示

代码实现

1
2
3
4
5
6
7
8
9
def insertionSort(arr):
    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
        arr[preIndex+1] = current
    return arr

希尔排序(Shell Sort)

1959年Shell发明，第一个突破$O(n^2)$的排序算法，是简单插入排序的改进版，它与插入排序的不同之处在于，它会优先比较距离较远的元素，希尔排序又叫缩小增量排序

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
  2. 按增量序列个数k，对序列进行k趟排序
  3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import math

def shellSort(arr):
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    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 = math.floor(gap/3)
    return arr

归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序

若将两个有序表合并成一个有序表，称为2-路归并

算法描述

  1. 把长度为n的输入序列分成两个长度为n/2的子序列
  2. 对这两个子序列分别采用归并排序
  3. 将两个排序好的子序列合并成一个最终的排序序列

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

快速排序(Quick Sort)

基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)，具体算法描述如下：

  1. 从数列中挑出一个元素，称为基准(pivot)
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)，在这个分区退出之后，该基准就处于数列的中间位置，这个称为分区(partition)操作
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

动图演示

具体过程，图片来源

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

堆排序(Heap Sort)

堆排序(Heapsort)是利用堆这种数据结构所设计的一种排序算法

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点

算法描述

  1. 将初始待排序关键字序列(R1, R2 …. Rn)构建成大顶堆，此堆为初始的无序区
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1, R2, … Rn-1)和新的有序区(Rn)，且满足R[1, 2 … n-1]<=R[n]
  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)，不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成

动图演示

代码实现

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 buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

非比较类

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶
  • 计数排序：每个桶只存储单一键值
  • 桶排序：每个桶存储一定范围的数值

计数排序(Counting Sort)

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数

算法描述

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  3. 对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)
  4. 反向填充目标数组: 将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

优缺点

  1. 当数列最大最小值差距过大时，并不适用计数排序
  2. 当数列元素不是整数，并不适用计数排序

优化版本的计数排序属于稳定排序

桶排序(Bucket Sort)

桶排序是计数排序的升级版，它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定

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

算法描述

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

图片演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
def bucket_sort(array):
    min_num, max_num = min(array), max(array)
    bucket_num = (max_num-min_num)//3 + 1
    buckets = [[] for _ in range(int(bucket_num))]
    for num in array:
        buckets[int((num-min_num)//3)].append(num)
    new_array = list()
    for i in buckets:
        for j in sorted(i):
            new_array.append(j)
    return new_array

基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序

最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前

算法描述

  1. 取得数组中的最大数，并取得位数
  2. arr为原始数组，从最低位开始取每个位组成radix数组
  3. 对radix进行计数排序(利用计数排序适用于小范围数的特点)

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def radix_sort(array):
    max_num = max(array)
    place = 1
    while max_num >= 10**place:
        place += 1
    for i in range(place):
        buckets = [[] for _ in range(10)]
        for num in array:
            radix = int(num/(10**i) % 10)
            buckets[radix].append(num)
        j = 0
        for k in range(10):
            for num in buckets[k]:
                array[j] = num
                j += 1

总结

使用场景

  • 如果待排序列中数据含有大量重复值——优先使用计数排序

  • 如果待排序列中数据近乎有序——优先使用插入排序

  • 如果待排序列中数据取值范围有限——优先使用计数排序
  • 如果待排序列中数据要求稳定——优先使用归并排序
  • 如果待排序列需要使用链表——优先链表归并、链表快排
  • 如果待排序列中数据无法全部装到内存——优先使用外部排序

优缺点

xxx