稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现的规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
常见排序算法可以分为两大类：
| 比较类排序 | 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 |
| 非比较类排序 | 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 |
比较性质排序算法的时间复杂度有一个理论边界，即 \(O(nlog_2n)\)。n个元素的序列，能够形成的所有排列个数为n!，即该序列构成的决策树叶子节点个数为n!。由叶子节点个数可知，决策树的高度为\(log_2n\)，即由决策树根节点到叶子节点的比较次数为\(log_2n\)。由斯特灵公式，\(n!\approx \sqrt{2\pi n} (\frac{n}{e})^{n}\)转换可得，比较性质的算法复杂度理论边界为\(O(nlog_2n)\)。
| 排序方法 | 稳定性 | 时间复杂度(最好) | 时间复杂度(平均) | 时间复杂度(最坏) | 空间复杂度 |
|---|---|---|---|---|---|
| 冒泡排序 | 稳定 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) |
| 快速排序 | 不稳定 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) |
| 简单插入排序 | 稳定 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) |
| 希尔排序 | 不稳定 | \(O(n)\) | \(O(n^{1.3})\) | \(O(n^2)\) | \(O(1)\) |
| 简单选择排序 | 不稳定 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) |
| 堆排序 | 不稳定 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(1)\) |
| 归并排序 | 稳定 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(n)\) |
| --- | --- | --- | --- | --- | --- |
| 计数排序 | 稳定 | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) |
| 桶排序 | 稳定 | \(O(n)\) | \(O(n+k)\) | \(O(n^2)\) | \(O(n+k)\) |
| 基数排序 | 稳定 | \(O(n * k)\) | \(O(n * k)\) | \(O(n * k)\) | \(O(n+k)\) |
?
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
?
Bubble Sort-python
def bubble_sort(nums):
for i in range(len(nums)):
j=0
while j < len(nums)-1-i:
if nums[j]>nums[j+1]:
nums[j],nums[j+1]=nums[j+1],nums[j]
j+=1
return nums
?
稳定性：稳定时间复杂度(最好): \(O(n)\)时间复杂度(平均): \(O(n^2)\)时间复杂度(最坏): \(O(n^2)\)空间复杂度: \(O(1)\)
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
def selection_sort(nums):
for i in range(len(nums)):
minIndex = i
for j in range(i + 1, len(nums)):
minIndex = j if nums[j] < nums[minIndex] else minIndex
if minIndex != i:
nums[i], nums[minIndex] = nums[minIndex], nums[i]
return nums
?
稳定性：不稳定时间复杂度(最好): \(O(n^2)\)时间复杂度(平均): \(O(n^2)\)时间复杂度(最坏): \(O(n^2)\)空间复杂度: \(O(1)\)
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
def insertion_sort(nums):
for i in range(1,len(nums)):
current=nums[i]
preIndex=i-1
while (preIndex>=0 and nums[preIndex]>current):
nums[preIndex+1]=nums[preIndex]
preIndex-=1
nums[preIndex+1]=current
return nums
?
稳定性：稳定时间复杂度(最好): \(O(n)\)时间复杂度(平均): \(O(n^2)\)时间复杂度(最坏): \(O(n^2)\)空间复杂度: \(O(1)\)
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版，但希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：
它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
增量 gap 的确定方法：
希尔算法的性能与所选取的增量（分组长度）序列有很大关系。只对特定的待排序记录序列，可以准确地估算比较次数和移动次数。想要弄清比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。一般常用的是 : gap=3 * gap+1 ——兼顾奇偶? 如果gap比较大，那么子序列会很小，用插入效率高? 如果gap很小，这时候数组基本有序，插入效率高
def shell_sort(nums):
gap=1
while gap < len(nums)/3:
gap=3*gap+1
while gap > 0:
for i in range(gap,len(nums)):
current=nums[i]
preIndex=i-gap
while preIndex>=0 and nums[preIndex]>current:
nums[preIndex+gap]=nums[preIndex]
preIndex-=gap
nums[preIndex+gap]=current
gap=gap//3
return nums
?
稳定性：不稳定时间复杂度(最好): \(O(n)\)时间复杂度(平均): \(O(n^{1.3})\)时间复杂度(最坏): \(O(n^2)\)空间复杂度: \(O(1)\)
快速排序是对冒泡排序的一种改进。快速排序的基本思想是：通过一趟排序，将待排记录分割成独立的两部分，其中左半部分均比右半部分小。（也就是找枢轴的正确索引）
假设待排序的序列为\([a_1,a_2,a_3,...,a_n]\):
# 一趟快速排序（或一次划分）
def partition(nums, low, high):
pivotVal = nums[low]
while low < high:
while nums[high] > pivotVal and high > low:
high -= 1
nums[low] = nums[high]
while nums[low] < pivotVal and low < high:
low += 1
nums[high] = nums[low]
nums[low] = pivotVal
return low
# 将划分后的子序列递归的进行快速排序
def qSort(nums, low, high):
if (low < high):
pivotKey = partition(nums, low, high)
qSort(nums, low, pivotKey - 1)
qSort(nums, pivotKey + 1, high)
return nums
def quick_sort(nums):
return qSort(nums, 0, len(nums) - 1)
?
稳定性：稳定时间复杂度(最好):\(O(nlog_2n)\)时间复杂度(平均): \(O(nlog_2n)\)时间复杂度(最坏): \(O(n^2)\)空间复杂度: \(O(nlog_2n)\)
快速排序需要一个栈空间来实现递归。若每一堂排序都将序列均匀均匀地分割成长度相接近的两个子序列，则栈的最大深度为\(\left \lfloor log_2n \right \rfloor+1\)(包括最外层参数进栈)。但是，若每趟排序之后，枢轴位置均偏向子序列的一端，则为最坏情况，栈的最大深度为n。如果改写上面算法代码，在一趟排序之后，比较分割所得两部分的长度，且先对长度短的子序列中的记录进行快速排序，则栈的最大深度可降为\(O(log_2n)\)
?
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
def heaptify(nums, tailIndex):
for i in range(tailIndex, 0, -1):
parent = (i - 1) // 2
if parent < 0:
break
if nums[i] > nums[parent]:
nums[i], nums[parent] = nums[parent], nums[i]
return nums
def heap_sort(nums):
for i in range(len(nums)):
tailIndex = len(nums) - 1 - i # tailIndex后为有序区
nums = heaptify(nums, tailIndex) # 堆化
nums[0], nums[tailIndex] = nums[tailIndex], nums[0]
return nums
?
稳定性：不稳定时间复杂度(最好): \(O(n)\)时间复杂度(平均): \(O(n^2)\)时间复杂度(最坏): \(O(n^2)\)空间复杂度: \(O(1)\)
计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。
由此可知，计数排序只适用于元素值较为集中的情况，若集合中存在最大最小元素值相差甚远的情况，则计数排序开销较大、性能较差。通过额外空间的作用方式可知，额外空间存储元素信息是通过计算元素与最小元素值的差值作为下标来完成的，若待排序集合中存在元素值为浮点数形式或其他形式，则需要对元素值或元素差值做变换，以保证所有差值都为一个非负整数形式。
def counting_sort(nums):
maxNum, minNum = max(nums), min(nums)
aux = [0] * (maxNum - minNum + 1)
minIndex = 0 - minNum
for i in range(len(nums)):
aux[minIndex + nums[i]] += 1
pointer = 0
for i in range(len(aux)):
while aux[i] > 0:
nums[pointer] = i - minIndex
aux[i] -= 1
pointer += 1
return nums
def counting_sort(nums):
maxNum, minNum = max(nums), min(nums)
aux = [0] * (maxNum - minNum + 1)
minIndex = 0 - minNum
for i in range(len(nums)):
aux[minIndex + nums[i]] += 1
for i in range(1, len(aux)):
aux[i] += aux[i - 1]
target = [None] * len(nums)
for i in range(len(nums) - 1, -1, -1):
targetIndex = aux[nums[i] + minIndex] - 1
target[targetIndex] = nums[i]
aux[nums[i] + minIndex] -= 1
return target
?
稳定性：稳定时间复杂度(最好): \(O(n+k)\)时间复杂度(平均): \(O(n+k)\)时间复杂度(最坏): \(O(n+k)\)空间复杂度: \(O(n+k)\)
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
def bucket_sort(nums, bucket_size):
minNum, maxNum = min(nums), max(nums)
bucketNum = (maxNum - minNum) // bucket_size + 1
buckets = [[] for x in range(bucketNum)]
for i in range(len(nums)):
buckets[(nums[i] - minNum) // bucket_size].append(nums[i])
result = []
for bucket in buckets:
if bucket:
shell_sort(bucket) # 用上面提到过的希尔排序算法
result += bucket
return result
?
稳定性：稳定时间复杂度(最好): \(O(n)\)时间复杂度(平均): \(O(n+k)\)时间复杂度(最坏): \(O(n^2)\)空间复杂度: \(O(n+k)\)
很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
一般情况下，假设有n个记录的序列：\([a_1,a_2,...,a_n]\)且每个记录\(a_i\)含有d个关键字（\(key_{i}^{0},key_{i}^{1},...,key_{i}^{d-1}\)，其中\(key^{0}\)称为最主位关键字，\(key^{d-1}\)称为最次位关键字）。若对于序列中任意两个记录\(a_i\)和\(a_j\)都满足下列有序关系：\[(key_{i}^{0},key_{i}^{1},...,key_{i}^{d-1})<(key_{j}^{0},key_{j}^{1},...,key_{j}^{d-1})\]
则称序列\([a_1,a_2,...,a_n]\)对关键字（\(key^{0},key^{1},...,key^{d-1}\)）有序。
为了实现多关键字排序，通常用两种方法:
最低位优先法 (Least Significant Digit first, LSD)
① 先对最次位关键字\(key^{d-1}\)进行排序。② 再按\(key^{d-2}\)划分为更小的子序列③ 依次重复，直至对\(key^{0}\)进行排序后便成为有序序列。
两种方法的特点：
① 若按MSD进行排序，必须将序列逐层分割成若干子序列，然后对各个子序列方别进行排序。② 而按LSD进行排序时，不必分成子序列，对每个关键字\(key^{i}\)都是整个序列参加排序，但只能用稳定的排序方法。③ 另外，按LSD进行排序时，在一定条件下(对前一个关键字\(key^{i},i\leq i \leq d-2\)的不同值，后一个关键字\(key^{i+1}\)均取相同值)，也可以不利用前面所提到的排序方法，而是通过若干次“分配”和“收集”来实现排序。
def Distribute(nums, key):
# 由于对数值排序，基数为10（0,1,2,......,9）
radixList = [[] for i in range(10)]
for i in range(len(nums)):
current = nums[i]
for _ in range(key):
index = current % 10
current //= 10
radixList[index].append(nums[i])
return radixList
def Collection(nums, radixList):
pointer = 0
for radixNums in radixList:
for num in radixNums:
nums[pointer] = num
pointer += 1
return nums
def radix_sort(nums):
maxNum = max(nums)
d = 0
# 确定关键字个数：个位（1位），十位(2位)，百位(3位)，千位(4位)........
while maxNum > 0:
d += 1
maxNum //= 10
for key in range(1, d + 1): # 按低位优先LSD依次对各个关键字进行分配和收集
radixList = Distribute(nums, key)
nums = Collection(nums, radixList)
return nums
?
稳定性：稳定时间复杂度(最好): \(O(n * k)\)时间复杂度(平均): \(O(n * k)\)时间复杂度(最坏): \(O(n * k)\)空间复杂度: \(O(n+k)\)
?
十大经典排序算法（动图演示）
【图解数据结构】 一组动画彻底理解基数排序
原文：https://www.cnblogs.com/weixia14/p/11519862.html