文章目录
- 前言
- 一、冒泡排序（Bubble Sort）
- 二、选择排序（Selection Sort）
- 三、插入排序（Insertion Sort）
- 四、希尔排序
- 五、快速排序（Quick Sort）
- 六、归并排序（Merge Sort）
- 七、堆排序（Heap Sort）
- 八、计数排序（Counting Sort）
- 九、桶排序（Bucket Sort）
- 十、 基数排序（Radix Sort）
前言
排序算法是计算机科学的核心基石，本文带您领略十大经典排序算法的精髓。文章以思维导图为线索，系统介绍两类主要排序方法：非线性时间比较类排序与线性时间非比较类排序。前者涵盖冒泡、快速、归并等经典算法，通过元素比较实现排序；后者如计数、桶、基数排序，则利用数据特性或额外空间实现高效排序。通过图文示例与详尽代码，可以更直观的理解算法思想与实现细节。
一、冒泡排序（Bubble Sort）
1.1 冒泡排序原理
相邻元素，比较大小，如果顺序不符合规则，则交换位置。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
1.2 冒泡排序代码
# 冒泡排序
alist = [3,2,5,9,10,1,6,8,2,4]
ln = len(alist)
for i in range(0,ln-1):
for j in range(0,ln-1-i):
if alist[j] > alist[j+1]:
alist[j],alist[j+1] = alist[j+1],alist[j]
print(alist)
print(f"第{i+1}轮：",alist)
print("-------完毕-------")
print(alist)
PS：每一轮排序确定一个最终位置
1.3 输出结果
>>> 输出结果：
[2, 3, 5, 9, 10, 1, 6, 8, 2, 4]
[2, 3, 5, 9, 10, 1, 6, 8, 2, 4]
[2, 3, 5, 9, 10, 1, 6, 8, 2, 4]
[2, 3, 5, 9, 10, 1, 6, 8, 2, 4]
[2, 3, 5, 9, 1, 10, 6, 8, 2, 4]
[2, 3, 5, 9, 1, 6, 10, 8, 2, 4]
[2, 3, 5, 9, 1, 6, 8, 10, 2, 4]
[2, 3, 5, 9, 1, 6, 8, 2, 10, 4]
[2, 3, 5, 9, 1, 6, 8, 2, 4, 10]
第1轮： [2, 3, 5, 9, 1, 6, 8, 2, 4, 10]
[2, 3, 5, 9, 1, 6, 8, 2, 4, 10]
[2, 3, 5, 9, 1, 6, 8, 2, 4, 10]
[2, 3, 5, 9, 1, 6, 8, 2, 4, 10]
[2, 3, 5, 1, 9, 6, 8, 2, 4, 10]
[2, 3, 5, 1, 6, 9, 8, 2, 4, 10]
[2, 3, 5, 1, 6, 8, 9, 2, 4, 10]
[2, 3, 5, 1, 6, 8, 2, 9, 4, 10]
[2, 3, 5, 1, 6, 8, 2, 4, 9, 10]
第2轮： [2, 3, 5, 1, 6, 8, 2, 4, 9, 10]
[2, 3, 5, 1, 6, 8, 2, 4, 9, 10]
[2, 3, 5, 1, 6, 8, 2, 4, 9, 10]
[2, 3, 1, 5, 6, 8, 2, 4, 9, 10]
[2, 3, 1, 5, 6, 8, 2, 4, 9, 10]
[2, 3, 1, 5, 6, 8, 2, 4, 9, 10]
[2, 3, 1, 5, 6, 2, 8, 4, 9, 10]
[2, 3, 1, 5, 6, 2, 4, 8, 9, 10]
第3轮： [2, 3, 1, 5, 6, 2, 4, 8, 9, 10]
[2, 3, 1, 5, 6, 2, 4, 8, 9, 10]
[2, 1, 3, 5, 6, 2, 4, 8, 9, 10]
[2, 1, 3, 5, 6, 2, 4, 8, 9, 10]
[2, 1, 3, 5, 6, 2, 4, 8, 9, 10]
[2, 1, 3, 5, 2, 6, 4, 8, 9, 10]
[2, 1, 3, 5, 2, 4, 6, 8, 9, 10]
第4轮： [2, 1, 3, 5, 2, 4, 6, 8, 9, 10]
[1, 2, 3, 5, 2, 4, 6, 8, 9, 10]
[1, 2, 3, 5, 2, 4, 6, 8, 9, 10]
[1, 2, 3, 5, 2, 4, 6, 8, 9, 10]
[1, 2, 3, 2, 5, 4, 6, 8, 9, 10]
[1, 2, 3, 2, 4, 5, 6, 8, 9, 10]
第5轮： [1, 2, 3, 2, 4, 5, 6, 8, 9, 10]
[1, 2, 3, 2, 4, 5, 6, 8, 9, 10]
[1, 2, 3, 2, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
第6轮： [1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
第7轮： [1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
第8轮： [1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
第9轮： [1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
-------完毕-------
[1, 2, 2, 3, 4, 5, 6, 8, 9, 10]
二、选择排序（Selection Sort）
2.1 选择排序原理
在未排序的序列中，找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中，继续寻找最小元素，放到已经排序序列的末尾。以此类推，直到所有元素均排序完毕。
序列最小的数字放到index=0的位置，未排序的序列越来越短，长度为0时，排序完毕。
2.2 选择排序代码
A = [12,22,15,1,8]
def selectSort(list):
for i in range(len(list)-1):
min = i
for j in range(i+1, len(list)):
if list[j]<list[min]:
min = j
list[min],list[i] = list[i], list[min]
print(f"第{i+1}轮排序结果：{list}")
return list
print(selectSort(A))
PS：每一轮排序确定一个最终位置
2.3 输出结果
>>> 输出结果：
第1轮排序结果：[1, 22, 15, 12, 8]
第2轮排序结果：[1, 8, 15, 12, 22]
第3轮排序结果：[1, 8, 12, 15, 22]
第4轮排序结果：[1, 8, 12, 15, 22]
[1, 8, 12, 15, 22]
三、插入排序（Insertion Sort）
3.1 插入排序原理
构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
实现逻辑
① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤
3.2 插入排序代码
def insertion_sort(arr):
# 第一层for表示循环插入的遍数
for i in range(1, len(arr)):
# 当前需要插入的元素
current = arr[i]
# 与当前元素比较的比较元素
pre_index = i - 1
while pre_index >= 0 and arr[pre_index] > current:
# 当比较元素大于当前元素则把比较元素后移
arr[pre_index + 1] = arr[pre_index]
# 往前选择下一个比较元素
pre_index -= 1
# 当比较元素小于当前元素，则将当前元素插入在 其后面
arr[pre_index + 1] = current
print(f"第{i}次插入后的结果为: {arr}")
return arr
A = [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
B = insertion_sort(A)
print(B)
PS：每一轮排序后的元素位置与最终元素位置肯可能不同
3.3 输出结果
四、希尔排序
4.1 希尔排序原理
希尔排序(Shell’s Sort) 是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。它与插入排序的不同之处在于，它会优先比较距离较远的元素， 该方法因D.L.Shell于1959年提出而得名。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
4.2 希尔排序代码
def shell_sort(arr):
# 取整计算增量（间隔）值 （每次缩小一半）
gap = len(arr) // 2
while gap > 0:
# 从增量值开始遍历比较
for i in range(gap, len(arr)):
j = i
current = arr[i]
# 元素与他同列的前面的每个元素比较，如果比前面的小则互换,其实，这就是插入排序
while j - gap >= 0 and current < arr[j - gap]:
arr[j] = arr[j - gap]
j -= gap
arr[j] = current
# 缩小增量（间隔）值
gap //= 2
print(f"第i轮排序结果：{arr}")
return arr
print("待排序序列：[3,1,8,9,2,6,0,8]")
sorted_arr = shell_sort([3,1,8,9,2,6,0,8])
print(sorted_arr)
PS：每一轮排序不能确定一个最终位置
三趟排序使用的gap（间隔）值，从远处到近处，依次比较
- ① gap=4
- ② gap=2
- ③ gap=1
4.3 输出结果
待排序序列：[3,1,8,9,2,6,0,8]
第i轮排序结果：[2, 1, 0, 8, 3, 6, 8, 9]
第i轮排序结果：[0, 1, 2, 6, 3, 8, 8, 9]
第i轮排序结果：[0, 1, 2, 3, 6, 8, 8, 9]
[0, 1, 2, 3, 6, 8, 8, 9]
五、快速排序（Quick Sort）
5.1 快速排序原理
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conquer Method)。
快速排序的基本原理是：
- 先从数列中取出一个数作为基准数。(可以是第一个、最后一个、中间的或者干脆随机的）
- 分区过程，将比这个基准数大的数全放到它的右边，小于的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
5.1.1 分治算法
什么是分治算法？
字面解释是“分而治之”，即把一个复杂的问题，分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，如此下去，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法的基本步骤
- 分解
将原问题分为若干个规模较小，相互独立，与原问题形式相同的子问题。 - 解决
如果子问题规模较小且容易背解决，则直接解决；否则递归地解各个子问题 - 合并
将各个子问题的解合并为原问题的解。
5.2 快速排序代码
import random
class SortUtil:
def quickSort(self,alist):
if not alist:
return alist
pivot = random.choice(alist)
print(f"枢轴元素:{pivot}")
equalList=[]
smallerList=[]
biggerList=[]
for item in alist:
if item < pivot:
smallerList.append(item)
elif item == pivot:
equalList.append(item)
else:
biggerList.append(item)
print(f"比枢轴元素大的:{biggerList}",f"\t与枢轴元素相等的:{equalList}",f"\t比枢轴元素小的:{smallerList}")
return self.quickSort(biggerList)+equalList+self.quickSort(smallerList)
# 待排序列表
a = [3,1,8,9,2,6,0]
su = SortUtil()
blist = su.quickSort(a)
# 排序之后输出
print(blist)
PS：每次都能确定一个最终位置
5.3 输出结果
六、归并排序（Merge Sort）
6.1 归并排序原理
归并排序采用分治法，思想是：先递归拆分数组为两半，再合并数组。
- 拆分数组
假设数组一共有 n 个元素，我们递归对数组进行折半拆分即 n//2 ，直到每组只有一个元素为止。 - 合并数组
算法会从最小数组开始有序合并，这样合并出来的数组一直是有序的，所以合并两个有序数组是归并算法的核心。
6.2 归并排序代码
def merge_sort(lst):
#递归结束条件
if len(lst) <= 1:
return lst
#分解问题,并递归调用
middle = len(lst)//2
left = merge_sort(lst[:middle])
right = merge_sort(lst[middle:])
#合并左右半部分，完成排序
merged_lst = []
while left and right:
if left[0] <= right[0]: #升序排列时，"="可以保证稳定性
merged_lst.append(left.pop(0))
else:
merged_lst.append(right.pop(0))
#如果左部分或右部分还有剩余，那就拼接到已排好序的列表中
merged_lst.extend(right if right else left)
return merged_lst
A = [11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
B = merge_sort(A)
print("待排序：",A)
print("已排序：",B)
6.3 输出结果
待排序： [11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
已排序： [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
七、堆排序（Heap Sort）
7.1 堆的概念
- 如果有一个关键码的集合
K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1且Ki<=K2i+2，则称为（小）堆。 - 堆（
heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树(逻辑层面上)的数组对象(物理层面上)。
7.2 堆排序
堆排序，顾名思义需要用到 堆 ，更具体的说是用到二叉堆。
二叉堆是一种特殊的完全二叉树，可分为以下两种：
- 大根堆：根节点的值最大，任何一个父节点的值，都
大于等于它左右孩子节点的值。 - 小根堆：根节点的值最小，任何一个父节点的值，都
小于等于它左右孩子节点的值。
python 中的二叉堆存储在列表中，依靠列表的下标来定位各个节点。
7.3 堆排序原理（+）
7.3.1 构建二叉堆
8,3,5,1,9,6，构建大根堆
步骤：
- 先得到无序完全二叉树
- 从最后一个非叶子节点调整节点
7.3.2 循环删除当前大根堆的堆顶
输出（pop）堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。
7.4 堆排序代码
# 堆排序
from heapq import heappush,heappop
def heapsort(iterable):
#排好序的存入这个列表里
h = []
#构建二叉堆
for value in iterable:
heappush(h, value)
#删除堆顶后，自我调整(堆的最后一个元素放到堆顶，下沉--)，再返回列表
return [heappop(h) for i in range(len(h))]
lst = [8,3,5,1,9,6]
lst2 = heapsort(lst)
print(lst2)
7.5 输出结果
待排序队列：[8, 3, 5, 1, 9, 6]
输出：[1, 3, 5, 6, 8, 9]
八、计数排序（Counting Sort）
8.1 计数排序原理
计数排序是一种线性时间复杂度(O(N))的非比较排序算法，它的基本思想是，对需要排序的数组中的元素进行统计，并构建一个辅助数组来保存每个元素在原始数组中出现的次数。然后，根据这些次数，将元素按照从小到大的顺序重新排列并返回结果。
统计序列中元素个数的排序，不是基于比较。适用于纯数字。
具体实现步骤如下：
- 统计需要排序的数据Array中的元素A[i]的出现次数。并将这些出现次数存储在另外一个长度为K的
数组C中，其中K=max{A[i]}+1。- 对所有的计数累加（从C[0]开始，每次与前面的和相加），得到新的C数组。
- 反向填充目标数组B：遍历A找到每个元素x，通过取出C[x]-1作为B的一个下标索引的方法来确定该
元素放置的正确位置，再将C[x]-1的值减1。- 返回排好序的目标数组B。
8.2 计数排序代码
def counting_sort(array):
largest = max(array); smallest = min(array) # 获取最大，最小值
counter = [0 for i in range(largest-smallest+1)] # 用于统计个数的空数组
idx = 0 # 桶内索引值
for i in range(len(array)):
counter[array[i]-smallest] += 1 # 统计每个元素出现的次数
for j in range(len(counter)):
while counter[j] > 0:
array[idx] = j + smallest # 取出元素
idx += 1
counter[j] -= 1
return array
A = [5,2,8,9,1,2]
counting_sort(A)
print(A)
8.3 输出结果
待排序队列：[5, 2, 8, 9, 1, 2]
输出队列：[1, 2, 2, 5, 8, 9]
优势
计数排序的优势在于它不需要进行任何的比较操作，而是通过把输入的数字映射到统计数组中来实现排序。因此，在处理大量相同重复数字的场景时，计数排序能够表现出良好的性能，甚至快于任何O(N*logN)时间复杂度排序算法。
同时，计数排序也具有稳定性、简单易于实现等优点。因此，在一些特殊场合下（例如对心电图信号进行分析、统计等），计数排序表现出了不错的效果。
九、桶排序（Bucket Sort）
9.1 桶排序原理
桶排序是一种常用的线性时间复杂度（O(N)）的排序算法，其基本思想是将需要排序的数据按照一定范围划分成若干个桶，每个桶内进行排序，最后按顺序将各个桶中的数据合并起来。 实际上，桶排序是对计数排序的升级版，它更适用于数据范围比较大的情况。
具体步骤如下：
- 找出待排序的数组中最大和最小的元素。
- 根据桶的数量，确定每个桶代表的数值范围，并且在这个范围内建立一个桶。
- 遍历原始数据，根据数据所处的区间，将数据分别放入对应的桶中。
- 对每个桶内的数据分别进行排序（可以使用任意排序算法），例如快速排序、插入排序等。
- 将所有的桶中的数据依次连接起来，得到最终的排序结果。
9.2 桶排序代码
def bucket_sort(arr):
n = len(arr)
if n <= 1:
return arr
max_val, min_val = max(arr), min(arr) # 找出最大和最小值
bucket_size = (max_val - min_val) // n + 1 # 确定桶的大小
bucket_num = (max_val - min_val) // bucket_size + 1 # 确定桶的数量
bucket = [[] for _ in range(bucket_num)] # 初始化桶
print("bucket_size：",bucket_size)
print("bucket_num：",bucket_num)
print("bucket：",bucket)
# 将数据分配到各个桶内
for i in range(n):
index = (arr[i] - min_val) // bucket_size
bucket[index].append(arr[i])
print("bucket-将数据分配到各个桶内：",bucket)
# 对每个桶中的数据进行排序，可选任意算法
for i in range(bucket_num):
if len(bucket[i]) > 0:
bucket[i].sort()
# 将排序后的数据依次连接起来
res = []
for i in range(bucket_num):
if len(bucket[i]) > 0:
res.extend(bucket[i])
print(f"第{i}次连接：{res}")
return res
lst = [1,7,9,5,1,2,8,4,2,6,10,8]
new_lst = bucket_sort(lst)
print(new_lst)
# output :[1, 1, 2, 2, 4, 5, 6, 7, 8, 8, 9, 10]
9.3 输出结果
bucket_size： 1
bucket_num： 10
bucket： [[], [], [], [], [], [], [], [], [], []]
bucket-将数据分配到各个桶内： [[1, 1], [2, 2], [], [4], [5], [6], [7], [8, 8], [9], [10]]
第0次连接：[1, 1]
第1次连接：[1, 1, 2, 2]
第2次连接：[1, 1, 2, 2]
第3次连接：[1, 1, 2, 2, 4]
第4次连接：[1, 1, 2, 2, 4, 5]
第5次连接：[1, 1, 2, 2, 4, 5, 6]
第6次连接：[1, 1, 2, 2, 4, 5, 6, 7]
第7次连接：[1, 1, 2, 2, 4, 5, 6, 7, 8, 8]
第8次连接：[1, 1, 2, 2, 4, 5, 6, 7, 8, 8, 9]
第9次连接：[1, 1, 2, 2, 4, 5, 6, 7, 8, 8, 9, 10]
输出结果：[1, 1, 2, 2, 4, 5, 6, 7, 8, 8, 9, 10]
注意，在使用桶排序时，需要保证元素之间有一定的均匀分布。如果元素之间过于集中，则可能导致某些桶内元素过多，从而影响性能。
十、 基数排序（Radix Sort）
10.1 基数排序原理
基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
基数排序的基本思想是： 将整数按位数切割成不同的数字，然后按每个位数进行比较。由于整数也可以表示字符串（如数字的字符表示），基数排序也可以扩展到非整数的排序，比如字符串的排序。
10.2 基数排序实例
实例讲解
假设我们有以下一组数字需要排序：[170, 45, 75, 90, 802, 24, 2, 66]。第一步：确定最大数的位数
在这个例子中，最大数是802，有三位数。
第二步：从最低位开始，依次进行排序
- 按个位排序：
- 使用计数排序（或其他稳定的排序算法）按个位数对数组进行排序。
- 排序后数组变为：[2, 24, 45, 66, 75, 90, 170, 802]（这里只展示了排序的结果，没有展示计数排序的过程）。
- 按十位排序：
- 注意，在按十位排序时，如果两个数的十位相同，则它们的相对位置应该和之前按个位排序时保持一致，以保证排序的稳定性。
- 使用计数排序或其他稳定的排序算法，但这次我们按十位数来分组和计数。
- 排序后数组可能变为：[2, 24, 45, 66, 75, 802, 90, 170]（注意，这里的排序可能需要根据实际的计数排序实现来调整，因为90和170的十位都是9和1，但在最终排序中它们的位置是基于百位和之前的排序结果的）。
- 按百位排序（如果有的话）：
- 同样使用计数排序，但按百位来分组和计数。
- 排序后数组最终为：[2, 24, 45, 66, 75, 90, 170, 802]。
基数排序通过“分配”和“收集”两个过程来实现排序，其中分配过程将元素分配到不同的桶中，收集过程则将桶中的元素合并回原数组。在实际应用中，计数排序经常被用作基数排序中的分配和收集过程。
def counting_sort_for_radix(arr, exp):
"""
用于基数排序中的计数排序子程序，根据当前位exp进行排序
:param arr: 输入的数组
:param exp: 当前考虑的位数（1表示个位，10表示十位，以此类推）
"""
n = len(arr)
# 输出数组，用于存放排序后的结果
output = [0] * n
# 计数数组，用于存放每个元素的出现次数
count = [0] * 10
# 存储arr中每个元素在当前位exp的值
for i in range(n):
index = arr[i] // exp
count[(index % 10)] += 1
# 更改count数组，现在它包含实际位置信息
for i in range(1, 10):
count[i] += count[i - 1]
# 构建输出数组
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[(index % 10)] - 1] = arr[i]
count[(index % 10)] -= 1
i -= 1
# 将排序后的数组拷贝回原数组，以便下一轮排序
for i in range(len(arr)):
arr[i] = output[i]
def radix_sort(arr):
"""
基数排序函数
:param arr: 输入的数组
"""
# 找到最大数以确定最大位数
max_val = max(arr)
# 对每个位数进行计数排序
exp = 1
while max_val // exp > 0:
counting_sort_for_radix(arr, exp)
exp *= 10
# 测试基数排序
if __name__ == "__main__":
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("排序后的数组:", arr)
