十种经典的排序算法的python实现（十大经典排序算法）

小君 2023-04-12 15:41:50 203

十种经典的排序算法的python实现（十大经典排序算法）def selection_sort(x start: int end: int): for i in range(start end 1): imin = i for j in range(i 1 end 1): if x[j] < x[imin]: imin = j x[i] x[imin] = x[imin] x[i]实现：每次找到最小值，放到目标位置。排序体系图每种算法复杂度汇总如下：说明:

概述

提示：本文上万字，陆陆续续疏理知识点加测试代码，耗时近一个月。阅读时长40分钟左右。

本文将十大经典排序算法进行汇总，从源码实现、复杂度、稳定性进行分析，并对每种排序的特性进行点评。对典型算法，给出了具体应用场景。

通俗地讲：

如果说插入排序是步步维艰的乌龟，那么希尔排序是跳跃的兔子，冒泡排序就是一个基本无用的小乌龟。选择排序，聊胜于无，比冒泡强一点点。
归并排序，将大问题分解成小问题，各个击破，分治思想的完整体现。老板拆解任务，下放给小兵解决，最后老板汇总上报。从国家到公司治理，这个套路很常见。
快速排序，人如其名，就是非常快！
堆排序，将一维数据建成高维的二叉树，有点“三体”维度打击的意思。

从技术体系上看，共两大类排序算法：

比较类排序：通过比较决定元素的相对顺序，理论上可证明：时间复杂度不能突破O(NlogN)的限制是非线性排序。
非比较类排序，可以突破比较排序的下界O(NlogN) 达到O(N) 故也称为线性排序。但有一些前提假设，后文会一一说明。

排序体系图

十种经典的排序算法的python实现（十大经典排序算法）(1)

每种算法复杂度汇总如下：

十种经典的排序算法的python实现（十大经典排序算法）(2)

说明:

N：输入序列长度
k: 桶个数
d: 最高位数(基数排序)

选择排序

每次找到最小值，放到目标位置。

十种经典的排序算法的python实现（十大经典排序算法）(3)

def selection_sort(x start: int end: int): for i in range(start end 1): imin = i for j in range(i 1 end 1): if x[j] < x[imin]: imin = j x[i] x[imin] = x[imin] x[i]

实现：

每次遍历确认x[i]的正确值
imin: [i end]中最小元素的index (参见示意图)

时间复杂度:

i j两层For循环最好最坏区间为[O(N^2) O(N^2)]
每次必须遍历完，才能确定最小值 avg/best/worst均为O(N^2)

空间复杂度：通过交换实现原址排序 O(1)

稳定性: 最后一行的 跨越交换 ，会打乱排序，不能保证稳定。比如[5 5 2]:

[5(1) 5(2) 2]
[2 5(2) 5(1)]

点评：最朴素的思想: 依次选出第一名、第二名、第三名

冒泡排序

逆序遍历，查看相邻元素，如果逆序，偏小值上浮。

def bubble_sort(x start: int end: int): for i in range(start end): swapped = False for j in range(end i -1): if x[j] < x[j - 1]: x[j] x[j - 1] = x[j - 1] x[j] swapped = True if not swapped: break def bubble_sort_raw(x start: int end: int): for i in range(start end): for j in range(end i -1): if x[j] < x[j - 1]: x[j] x[j - 1] = x[j - 1] x[j]

实现：

正序遍历，最大值下沉；或逆序遍历，最小值上浮。
通过检查当前遍历是否有过交换操作，如果无，表明已经排序好，可提前退出。

时间复杂度：

双层For循环，时间复杂度为O(N^2)
最好：数组已经排序好，可达到O(N)
平均、最坏：O(N2)

空间复杂度：原址排序，O(1)

稳定性：相邻的元素才可能交换，非跨越使交换，保证稳定。

点评：

频繁交换相邻元素，而不能跨越式地交换，是一个缺陷，但带来的好处是能实现稳定排序。和选择排序类似，遍历一遍，确定一个最小元素。
玩具算法，最简单但基本无用，唯一用法是快速判断一个数组是否已排序。很多新版教材都不提及。

插入排序

从前到后依次构建有序序列；对于待排序元素，在已排序列中从后向前扫描，找到对应位置插入。

十种经典的排序算法的python实现（十大经典排序算法）(4)

def insertion_sort(x start: int end: int): for i in range(start 1 end 1): j key = i - 1 x[i] while j >= start and key < x[j]: # swap only <(NOT<=) x[j 1] = x[j] # <--------- j -= 1 x[j 1] = key # <--------- def insertion_sort_vfor(x start: int end: int): # for-loop version for i in range(start 1 end 1): key = x[i] for j in range(i - 1 start - 1 -1): if key >= x[j]: # '='保证稳定性 x[j 1] = key # <-- x[j 1] break x[j 1] = x[j] # <-- x[j 1] else: x[j] = key # <-------- j==start def insertion_sort_vbubble(x start: int end: int): # bubble version slow but understandable for i in range(start 1 end 1): j = i while j >= start 1 and x[j] < x[j - 1]: x[j] x[j - 1] = x[j - 1] x[j] j -= 1

实现

将已经观察过的元素排序好，待观察元素往里插
每次都将x[j 1]赋值: 要么右移x[j 1]=x[j]; 要么x[j 1]=key

时间复杂度

最好：虽和选择排序位于O(N^2)同一梯队，但最好可达到O(N)，假设原序列已经排序好，只需要O(N)
最坏、平均：均为O(N^2)
拿当前处理位置i和之前的位置(i-1 i-2 …)比较如果大于或等于不交换。最好，只比较N次。

空间复杂度: O(1)

稳定性: 插入时的如果和历史元素值相同，不移动历史数据，能保证稳定

点评：

内层循环用while比for更简洁
对于短序列或近似排序好的序列，复杂度非常低

希尔排序

对子序列进行插入排序，实现最终排序（子序列步长递减），是对插入排序的优化。

十种经典的排序算法的python实现（十大经典排序算法）(5)

def shell_sort(x start: int end: int version="knuth"): n = end - start 1 h_list = gaps(n version=version) for h in h_list: for i in range(start h end 1): # h-sort j key = i - h x[i] while j >= start and key < x[j]: x[j h] = x[j] j -= h x[j h] = key def gaps(n: int version="knuth") -> List[int]: """ get the shell-sort gap list for length=n input sequence """ if version == "shell": h_list h = [] 1 # (3**k-1)//2 for k in [1 2 3 ...] while h < n // 2: # 1 4 13 40 121 364 1093 h_list.append(h) h = h * 2 else: # "knuth": # (3**k-1)//2 for k in [1 2 3 ...] h_list h = [] 1 while h < n // 3: # 1 4 13 40 121 364 1093 h_list.append(h) h = 3 * h 1 return h_list[::-1]

代码：

常用的步长序列：reverse(1 2 4 8 16 32 …)、reverse(1 4 13 40 121 364 1093 …)
理解：对间隔为h的子序列，分别应用插入排序
实现：从start h往后遍历一遍，交替地实现对间隔为h的多个子序列的插入排序

时间复杂度：

基于插入排序，最好最坏区间为：[O(N) O(N^2)/(N^1.5)] 取决于步长序列的设计
平均：O(N^1.2)

空间复杂度：O(1)

稳定性：虽基于插入排序，但是子序列导致排序不稳定

点评：

插入排序两个特征，一个优点是对于近似排好序的序列，复杂度很低；一个缺点是需要频繁移动相邻元素。希尔排序，扬长避短，充分利用插入排序的优点，避免插入排序的缺点。
通过对间隔为h的子序列排序，可快速交换，逐步让序列近似排好序过程中本质上还是插入排序，但不是笨笨的顺序遍历
如果说插入排序是乌龟，一步一步地移动；那么希尔排序就时兔子，可以几步几步地跳跃

快速排序

随机选取一个标杆元素，左边放小元素，右边放大元素，再递归对左边、右边的子序列快排。

十种经典的排序算法的python实现（十大经典排序算法）(6)

def quick_sort(x: Sequence start: int end: int): def partition(x start end) -> int: # Lomuto idx = int((start end) // 2) # random x[idx] x[end] = x[end] x[idx] m = start for i in range(start end): # without x[end] if x[i] < x[end]: x[i] x[m] = x[m] x[i] # <-------- m = 1 x[end] x[m] = x[m] x[end] # <--- i=end return m if start >= end: return m = partition(x start end) quick_sort(x start m - 1) quick_sort(x m 1 end) def quick_sort_hoare(x: Sequence start: int end: int): def partition(x start end) -> int: i j = start - 1 end 1 pivot = x[int((start end) // 2)] while True: j -= 1 while x[j] > pivot: j -= 1 i = 1 while x[i] < pivot: i = 1 if i < j: x[i] x[j] = x[j] x[i] else: return j if start >= end: return m = partition(x start end) quick_sort_hoare(x start m) quick_sort_hoare(x m 1 end)

代码:

由上而下编程，上层代码只有最后4行，加上partition()
函数核心是partition()

时间复杂度:

理想情况下，每次选取的x[end]都为中位数每次将长度N的原问题平均分为两个子问题达到最好的O(NlogN)
最坏情况下每次选取的x[end]都为最大值或最小值最坏为O(N^2)

空间复杂度: 通常实现为原址排序，平均空间复杂(函数调用栈空间，非尾递归，栈空间不能避免）为O(logN)

稳定性: 通常都是不稳定的(最后一次跨越交换导致)，也有稳定版本

点评：

partition有两个版本，Lomuto版易写；Hoare版通过双指针实现，容易出错，但交换次数会小些，标准库通常基于Hoare版本。
解决三色排序问题时，遍历一遍同时实现三个分区的划分标准库的排序算法，基本都是快速排序，因为快速排序的常数因子非常小

十种经典的排序算法的python实现（十大经典排序算法）(7)

三色排序的问题，请访问一次遍历，实现三色排序

归并排序

标准的分治思想：

分解：分解成长度相等的左右子序列
解决：递归调用归并排序，解决左右子问题
合并：合并排序好的左右子序列

十种经典的排序算法的python实现（十大经典排序算法）(8)

def merge_sort(x: Sequence start: int end: int): def merge(x start end): m = (start end) >> 1 left right = x[start:m 1] x[m 1:end 1] left.append(float('inf')) right.append(float('inf')) i_left i_right = 0 0 for i in range(start end 1): if left[i_left] <= right[i_right]: # <= 保证稳定性 x[i] = left[i_left] i_left = 1 else: x[i] = right[i_right] i_right = 1 if start >= end: return m = (start end) >> 1 merge_sort(x start m) merge_sort(x m 1 end) merge(x start end)

代码

顶层代码有5行，比quick_sort多出了合并的一行(分治=分解、解决、合并)
难点为merge(): 确保稳定性、用哨兵结点

时间复杂度:

利用多核高度并行化版本，可做到O(logN)
不同于quick_sort() 没有初始化的困惑，每次都严格2分最好最坏区间范围：[O(NlogN) O(NlogN)]

空间复杂度: 合并时，需要将left right合并到新空间，复杂为O(N) 无法直接覆盖原数组

稳定性:

当left和right中比较的两数相等时，优先选择left
因为left本身就比right靠前这样可以保证稳定

点评： 快排、归并排序: 均为分治算法，顶层结构一致（分解，解决，合并）

堆排序

优先队列和Top k问题中经常用到堆这种数据结构。本节介绍堆的基本性质、堆排序、优先队列、利用堆解决Top k问题。

堆的基本性质

堆，是具有下列性质的近似完全二叉树：每个节点的值都小于等于其左右孩子节点值是小根堆（大于等于则是大根堆）。

下图为大小为N=9的堆，高度、深度为log2(9)=3，为从根节点到叶结点的最长路径长度（边的个数）。根节点深度为0（相当于海平面），叶子结点深度最深。而高度的计算方式与深度相反，认为叶结点为地平面。

十种经典的排序算法的python实现（十大经典排序算法）(9)

父子关系满足：

left(i) = 2i 1
right(i) = 2i 2
parent(i) = (i-1)//2

十种经典的排序算法的python实现（十大经典排序算法）(10)

最后一个非叶结点index为parent(N-1) = (N-1-1)//2。故：

非叶结点范围：[0 N//2-1]
叶结点范围：[N//2 N-1]

堆化

建立堆(堆化)的过程：

从最后一个非叶结点开始，自底向上构建堆。
核心函数为heapify(x i) 假设i的左孩子、有孩子都满足堆的性质。以维护最小堆的性质为例：将i结点依次下沉所以复杂度为Height(i)。尾递归空间复杂可优化为O(1)，用循环实现

def build_min_heap(x): n = len(x) for i in range((n-2)//2 -1 -1): # 必须递减，满足heapify中孩子为堆的假设 min_heapify(x i n) def min_heapify(x i:int size:int): imin left right = i 2*i 1 2*i 2 if left<size and x[left]<x[imin]: imin=left if right<size and x[right]<x[imin]: imin=right if i!=imin: x[i] x[imin] = x[imin] x[i] min_heapify(x imin size)

建立堆复杂度为O(N)：

有1/2的元素向下比较了1次; 有1/4的元素向下比较了两次; …;
根据数学推导，可得比较次数<=2n

堆排序

构建最小堆，依次弹出堆顶元素
构建最大堆，首尾交换，size缩减1，堆顶元素下沉

def max_heapify(x i: int size: int): imax left right = i 2 * i 1 2 * i 2 if left < size and x[left] > x[imax]: imax = left if right < size and x[right] > x[imax]: imax = right if i != imax: x[i] x[imax] = x[imax] x[i] heapify(x imax size) def heap_sort(x): n = len(x) # build max-heap O(N) for i in range((n - 1 - 1) // 2 -1 -1): max_heapify(x i n) for i in range(n - 1 0 -1): # swap and siftdown O(NlogN) x[0] x[i] = x[i] x[0] max_heapify(x 0 size=i)

原址排序，时间复杂度O(NlogN)

实现：

建立最大堆：O(N)
首尾元素交换，然后堆大小缩减1，堆顶元素下沉：log(N) log(N-1) … = O(NlogN)

时间复杂度: O(N NlogN) = O(NlogN)

构建堆: 倒数第二层的元素每个比较1次，倒数底三层元素每个比较2次 …: 微积分计算可得O(N)
首尾元素交换，然后堆大小缩减1，堆顶元素下沉：log(N) log(N-1) … = O(NlogN)
heapify()维持堆的性质不变，即使已经排好序，首尾交换也会打乱，使得最好最坏复杂度[O(NlogN) O(NlogN)]

空间复杂度：O(1)如果heapify()递归实现，似乎也需要O(logN)的栈空间，但是是尾递归可优化为O(1)的迭代实现

稳定性：每次首尾交换跨越式交换，必然不稳定 [5 5 5]

点评：优先先队列、Top k问题，用堆排序非常合适

一种更加容易理解的堆排序(非原址、且建堆复杂度提高)方式如下：

import queue def heap_sort_using_pq(x start: int end: int): pq = queue.PriorityQueue() # 构建堆(优先队列) O(NlogN) for i in range(start end 1): pq.put(x[i]) for i in range(start end 1): # 弹出最小值 O(NlogN) x[i] = pq.get()

实现：

构建最小堆（优先队列）: O(NlogN)
依次弹出最小值（堆顶元素，并维护堆性质不变）: O(NlogN)

时间复杂度

O(2NlogN) = O(NlogN) 常数因子比原址排序大
从堆顶端拿出最值底部末尾拿一个最补上去每次POP的复杂度均为O(logN): O(NlogN)

空间复杂度为O(N)

稳定性：每次pop() 从顶端拿出一个末尾拿一个放上去必然不稳定 [5 5 5]

优先级队列

Python中，queue.PriorityQueue()是对heapq的OOP封装

put(item)
get()

核心源码如下：

from heapq import heappush heappop class PriorityQueue(Queue): '''Variant of Queue that retrie Entries are typically tuples of ''' def _init(self maxsize): self.queue = [] def _qsize(self): return len(self.queue) def _put(self item): heappush(self.queue item) def _get(self): return heappop(self.queue)

heapq源码解析

heapq.heapify(x) 即build_heap()假设左右子树都已经满足堆的性质一层一层下沉
heapq.heappush(e)堆尾部填入元素，一层一层上浮(该元素的祖已经排好序，进行插入排序 即可)
heapq.heappop()堆顶元素弹出堆底元素放入堆顶一层一层下沉(heapify(x i))

真正工业界的PQ 实现细节需要考虑清楚:

排序稳定性：你该如何令相同优先级的两个任务按它们最初被加入时的顺序返回？ A: 存储进入顺序

如果任务优先级发生改变，你该如何将其移至堆中的新位置？ A: 哈希表存储任务->value 将value标记为REMOVED 插入新的元素

或者如果一个挂起的任务需要被删除，你该如何找到它并将其移出队列？ A: 哈希表存储任务->value 将value标记为REMOVED 插入新的元素

利用堆，解决top k问题

top-k最小值是个常见问题。比如推荐排序中，给用户推荐用户最感兴趣的k个物品。一种本方法是利用快速排序，然后取前k个元素，复杂度为O(NlogN)。

更好地方法是利用堆。

一种方法是构建一个最小堆O(N)，然后取top-k O(klogN) 时间复杂度为 O(N klogN)，空间复杂度为O(N)

另外一种方法，构建大小为k的最大堆 heapq.nsmallest(k)采用的是这种方法，时间复杂度为O(k Nlogk klogk) 空间复杂度为O(k)。

想想你是一个功利的班主任，你拥有一间容量为k的教室，你需要从N多个学生中跳出Top k个好学生放进你的教室。

构建一个大小为k的最大堆O(k) [ 一个尖子班，人数限制为k ]
遍历元素，维护最大堆的性质：(Nlogk) [ 将其余同学依次插班到尖子班 ]如果该元素比最后一名好（小），则堆顶元素替换为该元素，并下沉 [ 只要与尖子班的最后一名比较，就能确认是否能进尖子班 ]
对最大堆元素进行快速排序(klogk)

点评：尖子班的最后一名很重要，用最大堆的堆顶，可快速获取最后一名

十种经典的排序算法的python实现（十大经典排序算法）(11)

桶排序

假设输入服从均匀分布，将数据划分到有限数量的桶里，每个桶内部分别排序。

def bucket_sort(x: List[float] k: int = None): # x ~ uniform [0 1) n = len(x) k = n if k is None else k buckets = [[] for _ in range(k)] for e in x: buckets[int(e * k)].append(e) # e//(1/k) 1/k is capacity of bucket for bucket in buckets: quick_sort(bucket 0 len(bucket) - 1) ans = [] for bucket in buckets: for e in bucket: ans.append(e) return ans

时间复杂度：

最好：数据服从均匀分布，均匀散落到每个桶，最好达到O(N)
最坏：数据严重偏离均匀分布，都算落到某一个桶中，取决于桶内排序算法的复杂度

空间复杂度：O(N k)

稳定性：取决于桶内排序算法的稳定性

点评：数据服从均匀分布、将其映射到[0 1) 区间

巧用桶排序，解决Leetcode上Hard的最大间距问题

计数排序

假设输入为[0 k]区间内的非负整数，将输入数据计数存储在新的序列中，然后逆序遍历输入序列，将该元素写入正确位置。

计数排序，是一种特殊的桶排序，每个桶最多有一个元素。

计数排序强制每个桶容积为1 k可以远大与N 所以时间、空间复杂度分析均为O(N k) k必不可少，比如：

x=[0 10000]
N=2
k=10000

def counting_sort(x: List[int]): k n = max(x) len(x) c ans = [0] * (k 1) [None] * n for e in x: # k -> count(k) c[e] = 1 for i in range(1 k 1): # k -> count(<=k) c[i] = c[i - 1] for j in range(n - 1 -1 -1): # stable sort ans[c[x[j]] - 1] = x[j] c[x[j]] -= 1 return ans

实现：计数计数累积逆序输出

时间复杂度：计数序列累积O(k) 两次遍历输入序列O(N) 所以时间复杂度区间为[O(N k) O(N k)]

空间复杂度：计数数组、输出序列占用空间为O(N k)

稳定性：最后一个For循环的逆序遍历输入，保证了稳定性

点评：输入的数据如果有确定范围的整数，通过偏移映射成[0 k]区间内的整数，可用计数排序

基数排序

先低位稳定排序，然后再高位稳定排序，直到最高位。

def counting_sort_for_radix(x: List[int] data: List): k n = max(x) len(x) c ans = [0] * (k 1) [None] * n for e in x: # k -> count(k) c[e] = 1 for i in range(1 k 1): # k -> count(<=k) c[i] = c[i - 1] for j in range(n - 1 -1 -1): # stable sort ans[c[x[j]] - 1] = data[j] # <---------- c[x[j]] -= 1 return ans def radix_sort(x): d = len(str(max(x))) for i in range(d): tmp = [e // (10**i) % 10 for e in x] x = counting_sort_for_radix(tmp x) return x

实现：