Chancel's blog
有善始者实繁，能克终者盖寡。
作者：Chancel Yang， 创建：2019-03-12， 字数：6522， 已阅：735， 最后更新：2024-03-10
现代大部分编程语言已经很少需要直接写排序算法了，但学习排序算法的原理依旧是一件非常有意思的事
下文是学习几个常见的排序算法笔记，如有错漏，请不吝指正
常见的算法概览如下
| 排序算法 | 是否稳定 | 最好时间复杂度 | 最差时间复杂度 | 平均时间复杂度 | 空间复杂度 |
|---|---|---|---|---|---|
| 冒泡排序(Bubble sort) | 是 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| 插入排序(Insertion sort) | 是 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| 希尔排序(Shell sort) | 否 | $O(n log n)$ | $O(n^2)$ | 取决于步长序列 | $O(1)$ |
| 快速排序(Quicksort) | 否 | $O(n log n)$ | $O(n^2)$ | $O(n log n)$ | $O(log n)$ |
| 选择排序(Selection sort) | 否 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| 归并排序(Merge sort) | 是 | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | $O(n)$ |
| 计数排序(Counting sort) | 是 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ |
这些复杂度的值是一般情况下的估计值，实际应用中可能会有所变化。
算法的稳定性是指对于待排序列中相同项的原来次序不能被算法改变则称该算法稳定，如按数字顺序来排序下列的组合
[(2, A), (1, B), (2, C), (3, D)]
那么在排序之后则会得到
[(1, B), (2, A), (2, C), (3, D)]
这里可以看到，在排序后，两个值为 2 的元素(2, A), (2, C)仍然保持了它们在原始序列中的相对顺序，我们称这种算法为稳定的排序算法
复杂度则区分时间复杂度（Time complexity）与空间复杂度（Space Complexity）
概念定义如下
时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大$O$符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指针，一般来说，空间复杂度越小，算法越好在不同的场景下，需要对时间和空间的复杂度有所取舍
常见的复杂度通常包含如下
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成
实现思路
Python代码实现如下
def bubble_sort(sort_list):
bubble_list_length = len(sort_list)
while bubble_list_length > 0:
for _i in range(0, bubble_list_length-1):
if sort_list[_i] > sort_list[_i + 1]:
sort_list[_i], sort_list[_i +
1] = sort_list[_i+1], sort_list[_i]
bubble_list_length -= 1
return sort_list
插入排序是一种简单直观的排序算法，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
实现思路
Python代码实现如下
def insert_sort(sort_list):
length = len(sort_list)
for i in range(1, length):
for j in range(i, 0, -1):
if sort_list[j] < sort_list[j-1]:
sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]
return sort_list
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是不稳定排序算法
实现思路
Python代码实现如下
def diminishing_increment_sort(sort_list):
length = len(sort_list)
h = 1
while h < length/3:
h = 3*h+1
while h >= 1:
for i in range(h, length):
j = i
while j >= h and sort_list[j] < sort_list[j-h]:
sort_list[j], sort_list[j-h] = sort_list[j-h], sort_list[j]
j -= h
h = h//3
return sort_list
快速排序又称划分交换排序（partition-exchange sort），简称快排。最早由东尼·霍尔提出。快速排序$O(nlogn)$通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分处理器架构上很有效率地达成。
快速排序的内部循环通常使用指针操作和元素交换，而不需要额外的数组或列表操作
实现思路
Python代码实现如下
def quick_sort(sort_list):
if len(sort_list) > 2:
mid = sort_list[0]
sort_list.remove(mid)
left_list = []
right_list = []
for i in range(0, len(sort_list)):
if sort_list[i] < mid:
left_list.append(sort_list[i])
if sort_list[i] > mid:
right_list.append(sort_list[i])
return quick_sort(left_list) + [mid] + quick_sort(right_list)
else:
return sort_list
选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
实现思路
Python代码实现如下
def selection_sort(sort_list):
def _select_min_number(temp_list):
if len(temp_list) is 0:
return None
min_number = temp_list[0]
for _n in temp_list:
if _n < min_number:
min_number = _n
return min_number
归并排序是创建在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
实现思路
Python代码实现如下
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
计数排序是一个非比较排序算法，该算法于1954年由 Harold H. Seward 提出。优势在于在对一定范围内的整数排序时，它的复杂度为$Ο(n+k)$（其中k是整数的范围），快于任何比较排序算法。
当然这是一种牺牲空间换取时间的做法，而且当$O(k)$>$O(nlog(n))$的时候其效率反而不如归并排序，堆排序等比较排序算法*
实现思路
Python代码实现如下
def counting_sort(sort_list):
length = len(sort_list)
new_list = [None]*length
for i in range(length):
p = 0
q = 0
for j in range(length):
if sort_list[j]<sort_list[i]:
p+=1
if sort_list[j]==sort_list[i]:
q+=1
for k in range(p,p+q):
new_list[k] = sort_list[i]
return new_list
参考资料