排序算法经过很长时间的演化，产生了很多不同的方法。虽然每一种的算法在时间和空间复杂度上各有不同，但是各种算法也都有不同的应用场景，并不是效率最高的算法就适应所有的使用场景。
下面我们来归纳一下我们常见的一些排序算法，已经这些算法的时间复杂度和空间复杂度，以及这些排序算法的稳定性。
按照大的分类，排序可以分为内排序和外排序。内排序是值在排序过程中，全部记录都是存放在内存中的。而外排序则是在排序过程中需要使用到外部存储。
我们下面总结的是内排序算法：
插入排序
选择排序
冒泡排序
快速排序
归并排序
希尔排序
基数排序
堆排序
插入排序
排序思想
插入排序是思想很简单，就是最初先把一个序列的第一个元素看成一个有序序列，然后把后面的序列看作无序序列。将后面无序序列中的元素逐个放到前面的有序序列中的合适位置。
排序过程示例
现有一个待排序的序列：
| 5 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|
5 | 4 | 8 | 3 | 7 | 3 | 6 |
首先，我们把[5,] 看作一个单独的有序序列，后面的[4,8,3,7,3,6]看作一个无序序列。
有序序列 = [5,]，
无序序列 = [4, 8, 3, 7, 3, 6]
然后选择将后面无序序列，现在我们把无序序列中的第一个元素放到有序序列的合适位置，然后
有序序列 = [4, 5,]，
无序序列 = [8, 3, 7, 3, 6]
经过一次排序后，序列变为：
| 4 | 5 | 8 | 3 | 7 | 3 | 6 |
|---|
然后再把前面继续前面类似的操作，将后面无序序列中的元素逐一加到有序序列中。最终完成排序过程。
python实现
# 插入排序算法 def insert_sort(array): for i in range(1, len(array)): j = i - 1 # array[0:j]是有序序列, array[i:]是无序序列 temp = array[i] # temp暂存待存入有序序列的数字 while j >= 0 and array[j] > temp: # 寻找有序序列中的合适位置 array[j+1] = array[j] # 如果当前数字大于待存入的temp，则把该数字后移一位 j -= 1 array[j+1] = temp # 将待排序的数字存到有序序列中的合适位置 return array
算法复杂度
时间复杂度：
最好的情况下，如果序列本来就是有序的，则不会进入到内部循环中，只有一层循环，时间复杂度是O(n)；最坏情况下，序列是反序的，则要完全运行两层循环，时间复杂度为O(n2)。平均时间复杂度为O(n2)。
空间复杂度：O(1)
算法稳定性
在排序过程中，是从无序序列的开始到结尾，一个一个与前面的有序序列中的元素做比较，因此该排序是稳定的。
选择排序
排序思想
从待排序的序列中找出最小的元素与第一个元素交换，然后再在剩下的序列中找出最小的元素与第二个元素交换，以此类推。。。直到最后一个元素
排序过程示例
现有一个待排序的序列
| 5 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|
首先，从头到尾找到最小的元素3；
然后，将3与第1个元素交换。
经过1次排序后，序列变为：
| 3 | 4 | 8 | 5 | 7 | 3 | 6 |
|---|
然后，在剩下的序列中找出最小的，也是3，与第2个元素交换，
经过2次排序后，序列变为：
| 3 | 3 | 8 | 5 | 7 | 4 | 6 |
|---|
然后，在剩下的序列中找出最小的，是4，与第3个元素交换。
经过2次排序后，序列变为：
| 3 | 3 | 4 | 5 | 7 | 8 | 6 |
|---|
。。。。。。
python实现
# 选择排序算法 def select_sort(array): array_len = len(array) for i in range(array_len): k = i for j in range(i, array_len): # 从头到尾找出最小的 if array[k] > array[j]: k = j array[i], array[k] = array[k], array[i] # 交换位置 return array
算法复杂度
时间复杂度：
排序的两层循环都需要走一遍，因此该算法安的最好的情况，最坏情况下和平均情况下的时间复杂度均为O(n2)。
空间复杂度：O(1)
算法稳定性
不稳定，比如序列[3,4,3,1,]，第1次排序时候，首尾两个数字交换，序列中两个3的相对位置就发生变化了。
冒泡排序
排序思想
排序思想是从第1个元素到第n个元素遍历，如果前一个元素大于后一个元素，则调换两者位置。这样经过一次排序后，最大的元素就排到了最后面。然后再从第1个元素到第n-的元素进行下一轮的冒泡排序
排序过程示例
现有一个待排序的序列
| 5 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|
首先，冒泡一次，第1个元素和第2个元素交换位置：
| 4 | 5 | 8 | 3 | 7 | 3 | 6 |
|---|
然后，一直相互对比，直到最后，
经过一轮冒泡之后，序列变为：
| 4 | 5 | 3 | 7 | 3 | 6 | 8 |
|---|
然后再继续第2轮的冒泡。
python实现
# 冒泡排序 def bubble_sort(array): array_len = len(array) for i in range(array_len): for j in range(array_len-i-1): if array[j] > array[j+1]: array[j], array[j+1] = array[j+1], array[j] return array
算法复杂度
时间复杂度：
冒泡排序与选择排序类似，无论序列情况，都需要完全走完两层for循环，最好，最坏和平均的时间复杂度都为O(n2)。
空间复杂度：O(1)
算法稳定性
冒泡排序时，相同的元素不会出现位置的调换，排序是稳定的。
快速排序
排序思想
先选取一个基准元素base，一般我们选择第1个元素，然后分别找两个指针left和right分别指向序列的第一个和最后一个元素，然后right往前面去找，找到一个小于基准元素的的元素，将该元素赋值给left所在位置;然后再从left位置继续往后找，找到一个大于基准元素的元素，然后将该元素赋值给right所在位置，然后再right往前。。。。。就这样left以此交替，直到left和right两者相遇。相遇后，则将原来标记的基准元素base赋值到该位置。
这样就将序列以base为界分为了前后两个部分，前一部分是小于基准元素的，后一部分是大于基准元素的。然后我们再分别对base前后的两个子序列按照以上相同的方式递归。最后整个序列就完成了排序了。
排序过程示例
现有一个待排序的序列
| 5 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|
首先，我们选取第1个元素为基准元素，赋值给变量base。然后分别定义两个指针left, right指向第一个元素和最后一个元素：
| 5 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|---|---|---|---|---|---|
| base left | - | - | - | - | - | right |
然后，先从right指针开始，判断指向的元素是否小于基准元素base，如果满足条件，则一个一个元素地持续向左移动，直到找到元素满足条件。如下：
base = 5
| 5 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|---|---|---|---|---|---|
| base left | - | - | - | - | right | - |
然后把right指向的元素赋值给base指向的元素。
base = 5
| 3 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|---|---|---|---|---|---|
| base left | - | - | - | - | right | - |
然后再从左向右移动left指针，直到找到一个大于base的元素：
base = 5
| 3 | 4 | 8 | 3 | 7 | 3 | 6 |
|---|---|---|---|---|---|---|
| base | - | left | - | - | right | - |
然后将left指向的元素赋值给right指向的元素：
base = 5
| 3 | 4 | 8 | 3 | 7 | 8 | 6 |
|---|---|---|---|---|---|---|
| base | - | left | right | - | - | - |
接下来，再去移动right指针，寻找小于base的元素，如果有，则赋值给此时left指向的元素：
base = 5
| 3 | 4 | 3 | 3 | 7 | 8 | 6 |
|---|---|---|---|---|---|---|
| base | - | left | right | - | - | - |
然后再移动left指针，寻找大于base的元素，如果有，赋值给right指向的元素。此时，对于我们的例子，left和right指针已相遇，则停止移动：
base = 5
| 3 | 4 | 3 | 3 | 7 | 8 | 6 |
|---|---|---|---|---|---|---|
| base | - | - | right left | - | - | - |
相遇后，则将base赋值给此时相遇的位置的元素：
base = 5
| 3 | 4 | 3 | 5 | 7 | 8 | 6 |
|---|---|---|---|---|---|---|
| base | - | - | right left | - | - | - |
于是，序列被base给分割成了两个部分，左边的全部小于5， 右边的全部大于5，然后，我们再继续对左半和右半边的元素按照相同的方式递归，直到最终完成所有元素的排序。
python实现
# 快速排序1 def partition(array, left, right): base = array[left] while left < right: while left < right and array[right] >= base: # 从右边找到第一个小于base的元素 right -= 1 array[left] = array[right] # 找到后，赋值给left所指位置 while left < right and array[left] <= base: # 从左边找到第一个大于base的元素 left += 1 array[right] = array[left] # 找到后，赋值给right所指的位置 array[left] = base # left和right相遇时，将base赋值到它们相遇的位置 return left # 返回中间分界点，此时左边的都小于base, 右边的都大于base def quick_sort(array, left, right): if left < right: mid = partition(array, left, right) quick_sort(array, left, mid-1) quick_sort(array, mid+1, right) return array
改进一下，可以将以上两个函数合并为一个，原理是一样的：
# 快速排序2 def quick_sort_2(array, left, right): if left >= right: return base = array[left] l, r = left, right while l < r: while l < r and array[r] >= base: r -= 1 while l < r and array[l] <= base: l += 1 if l < r: array[l], array[r] = array[r], array[l] array[left], array[l] = array[l], array[left] quick_sort_2(array, left, l-1) quick_sort_2(array, l+1, right)
另外，在网上看到一个很简短的快排的python实现：
def qsort(lst): if not lst: return [] return qsort([i for i in lst[1:] if i < lst[0]]) + [lst[0]] + qsort([i for i in lst[1:] if i > lst[0]])
算法复杂度
时间复杂度：
最好的情况下，每次都能将序列平均分为两份，这种情况下的时间复杂度就是O(N*log2N)；最坏情况下，每次划分都是一半是1个元素，另一半是n-1个元素，这种极端情况下的时间复杂度为O(n2)。平均时间复杂度为O(n2)。
空间复杂度：
每次都分出一半进行单独的排序，比较占用内存，最好情况下，空间复杂度为O(log2N)，最差情况下，空间复杂度为O(n)
算法稳定性
不稳定，比如[3,4,1,1]排序，可能会使原来两个1元素的相对位置发生变化。
归并排序
排序思想
归并排序的思想是将一个序列根据二分法分为两个序列，然后再将这两个序列一直二分下去，直到最后是单个元素，然后再对分出来的两个序列做合并，合并成一个局部有序的子序列，然后再继续向上合并，直到最终所有子序列合并，变成一个完全有序的序列。
排序过程示例
现有一个待排序的序列
| 5 | 8 | 4 | 3 | 7 | 3 | 6 |
|---|
首先，该序列有7个元素，可以分为
| 5 | 8 | 4 |
|---|
和
| 3 | 7 | 3 | 6 |
|---|
两个列表，再将前一个继续二分下去得到
| 5 |
|---|
和
| 8 | 4 |
|---|
然后，
| 8 | 4 |
|---|
继续二分得到
| 8 |
|---|
和
| 4 |
|---|
现在已经二分到了最小的单元，然后再进行归并排序
| 8 |
|---|
和
| 4 |
|---|
归并排序得到
| 4 | 8 |
|---|
得到的序列再和之前分出来的
| 5 |
|---|
进行归并排序得到
| 4 | 5 | 8 |
|---|
同样的，前面分出的另一半也通过上述归并排序得到
| 3 | 3 | 6 | 7 |
|---|
现在这两个子序列也都是局部有序的，再进行一个归并即可得到：
| 3 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|
python实现
# 归并排序 def merge(left, right): i, j = 0, 0 merged_array = [] while i < len(left) and j < len(right): # 将两个序列中元素从前面开始依次比较，从小到大归并进新序列 if left[i] <= right[j]: merged_array.append(left[i]) i += 1 else: merged_array.append(right[j]) j += 1 merged_array.extend(left[i:]) # 将序列中剩余的元素也归并进去 merged_array.extend(right[j:]) # 将序列中剩余的元素也归并进去 return merged_array def merge_sort(array): array_len = len(array) if array_len == 1: return array mid = array_len//2 # 将序列二分为两个部分 left = array[:mid] right = array[mid:] return merge(merge_sort(left), merge_sort(right)) # 递归调用
算法复杂度
时间复杂度：
始终需要对序列进行二分，然后合并，因此时时间复杂度在最好，最坏和平均情况下都为O(N*log2N)。平均时间复杂度为O(n2)。
空间复杂度：O(n), 序列越长，二分需要占用的内存越大。
算法稳定性
归并排序的算法是稳定的。
希尔排序
排序思想
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
排序过程示例
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时就是简单的插入排序了）。
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。
python实现
def shell_sort(array): array_len = len(array) step = array_len//2 while step >= 1: # 步长一直减半到1 for i in range(step, array_len): # 从第二行序列开始，以步长step为间隔进行插入排序 j = i - step temp = array[i] while j >= 0 and array[j] > temp: array[j+step] = array[j] j = j - step array[j+step] = temp step = step//2 # 步长减半 return array
算法复杂度
时间复杂度：
它的最好及最差时间复杂度和简单插入排序一样，分别是是O(n)和O(n2)，平均时间复杂度试增量选取规则而定，一般认为介于O(n)和O(n2)之间
空间复杂度：O(1)，不需要额外空间
算法稳定性
与直接插入排序不同，希尔排序是不稳定的。
基数排序
排序思想
基数排序是一种典型的空间换时间的排序方法。现在所有排序数字中找到最大的数字，确定它的位数，然后将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。接下来，依次从最低位到最高位，将该位的数字按照从小到大分配该数位的位置，然后再将这些数字依次收集回到待排序序列中，然后再对下一个位数进行如上操作，直到最高位。
排序过程示例
现有一个待排序的序列
| 17 | 254 | 34 | 3 | 22 | 5213 | 6 | 1000 |
|---|
首先，确定最大数字位5213，位数为4
然后，先从个位数开始，将这些数字存入到0-10的容器中：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1000 | 22 | 0003 5213 | 254 034 | 6 | 17 |
然后将这些数字再依次收集回来，得到的序列为：
| 1000 | 22 | 3 | 5213 | 254 | 34 | 6 | 17 |
|---|
经过这一轮的分配和收集之后，序列元素就按照最低位的数字从小到大排列了。
然后再根据第2位（十位）进行分配：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1000 0003 0006 | 5213 0017 | 22 | 34 | 254 |
然后再将这些元素收集：
| 1000 | 3 | 6 | 5213 | 17 | 22 | 34 | 254 |
|---|
重复上述步骤，直到最高位。即可完成序列的排序。
python实现
# 基数排序 def radix_sort(array): # 找到序列中最大的数 max_num = max(array) # 最大数的位数 bit_num = 0 while max_num > 0: bit_num += 1 max_num = max_num//10 # 最外层循环，每次循环按照位数分配并取回一次 for i in range(bit_num): # 建一个列表（列表元素也是一个列表），存储分配过来的数字 container = [[] for x in range(20)] # 将所有数字分配到列表中 for item in array: # 获取元素相应位数的数字 x = item % (10**(i+1))// (10**(i)) container[x].append(item) array = [] # 从0到10，依次将container列表中的元素取出来 for j in range(10): array.extend(container[j]) return array
算法复杂度
时间复杂度：
基数排序的最好，最好、最坏和平均时间复杂度都是O(n*r)，其中n是数据大小，r是所选基数。
空间复杂度：
O(n+r)的额外空间。它是稳定的。
算法稳定性
基数排序的算法是稳定的。
堆排序
排序思想
堆排序利用的是二叉树的思想，所谓堆就是一个完全二叉树，完全二叉树的意思就是，除了叶子节点，其它所有节点都有两个子节点，这样子的话，完全二叉树就可以用一个一块连续的内存空间（数组）来存储，而不需要指针操作了。堆排序分两个流程，首先是构建大顶堆，然后是从大顶堆中获取按逆序提取元素。
首先是大顶堆，大顶堆即一个完全二叉树，的每一个节点都大于它的所有子节点。大顶堆可以按照从上到下从左到右的顺序，用数组来存储，第i个节点的父节点序号为(i-1)/2，左子节点序号为2i+1，右子节点序号为2(i+1)。构建大顶堆的过程即从后向前遍历所有非叶子节点，若它小于左右子节点，则与左右子节点中最大的交换，然后递归地对原最大节点做同样的操作。
排序过程示例
现有一个待排序的序列
| 5 | 4 | 8 | 3 | 7 | 3 | 9 | 6 | 1 |
|---|
首先，列表以完全二叉树的形式如下图：
然后，从最后一个根节点开始，将它的左右子节点和根节点的值作比较，将最大的值放到根节点，如下：
接下来，按照上述调整方法，从后往前依次调整各个根节点，直到调整到最后：
这样，经过一轮后，最大的就被排到了最前面。
| 9 | 7 | 8 | 6 | 4 | 3 | 5 | 3 | 1 |
|---|
然后将该元素交换到序列末尾，序列就变成了：
| 1 | 7 | 8 | 6 | 4 | 3 | 5 | 3 | 9 |
|---|
最大的元素被排到了最后。
调换顺序之后，第一个元素的最大堆特征被破坏，然后对其进行调整。
重复以上步骤，直至元素全部调整为有序。
python实现
# 堆排序 def heap_sort(array): def heap_adjust(array, x, length): ''' 调整序列中的某个节点，array为待调整序列，x为待调整节点，length为序列长度 ''' left_chl, right_chl = 2*x + 1, 2*x + 2 # 节点x的左右子节点 max = x if left_chl < length and array[left_chl] > array[max]: max = left_chl if right_chl < length and array[right_chl] > array[max]: max = right_chl if max != x: array[x], array[max] = array[max], array[x] # 将较大的节点和父节点交换 # 交换后可能造成该节点下的子节点序列错乱，再次调整一下 heap_adjust(array, max, length) def build_heap(array): ''' 构建一个最大堆 ''' # 找出序列array指定长度length的切片的子序列中的最后一个根节点 # last_root_num = (length-1)//2 # For循环，从最后一个根节点以此往前调整，直到根节点 array_len = len(array) for i in range((array_len-1)//2, -1, -1): heap_adjust(array, i, array_len) array_len = len(array) # 构建最大堆 build_heap(array) for i in range(array_len-1, 0, -1): # 将构建好的最大堆中的第一个元素(最大)交换到最后一个位置。 array[i], array[0] = array[0], array[i] # 交换之后，调整剩下的序列为一个最大堆 heap_adjust(array, 0, i+1) return array
算法复杂度
时间复杂度：
在最好，最坏和平均情况下的时间复杂度都为O(N*log2N)
空间复杂度：O(1)
算法稳定性
不稳定
各个排序算法比较
下面对这几种排序算法的特点进行总结和比较：
| 排序算法 | 时间复杂度(最好) | 时间复杂度(最坏) | 时间复杂度(平均) | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 | 简单 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | 简单 |
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(1) | 不稳定 | 复杂 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | 复杂 |
| 希尔排序 | O(n) | O(n2) | O(n)~O(n2)(与步长有关) | O(1) | 不稳定 | 简单 |
| 基数排序 | O(n+r) | O(n+r) | O(n+r) | O(n) | 稳定 | 复杂 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | 复杂 |
下面，在序列长度不同的情况下，分别验证了各种排序算法耗时情况。
测试代码如下：
import datetime
def test_sort_time(func, num=1000):
import random
test_list = [x for x in random.sample([x for x in range(num)], num)]
start_time = datetime.datetime.now()
func(test_list)
end_time = datetime.datetime.now()
print("%s 排序耗时： %s" %(func.__name__, (end_time - start_time)))
num = 10000
test_sort_time(insert_sort, num)
test_sort_time(select_sort, num)
test_sort_time(bubble_sort, num)
# test_sort_time(quick_sort, num) # 快排的传参与其它的几个不同，我们测试快排时，需要稍微修改一下上述测试代码。
test_sort_time(merge_sort, num)
test_sort_time(shell_sort, num)
test_sort_time(radix_sort, num)
test_sort_time(heap_sort, num)最终测试，得到如下数据：
| 序列长度 | 插入排序 | 选择排序 | 冒泡排序 | 快速排序 | 归并排序 | 希尔排序 | 基数排序 | 堆排序 |
|---|---|---|---|---|---|---|---|---|
| 1000 | 0.039222 | 0.057428 | 0.083083 | 0.002998 | 0.0 | 0.015638 | 0.0 | 0.004994 |
| 10000 | 4.845310 | 4.377964 | 9.359449 | 0.039283 | 0.063264 | 0.056017 | 0.028226 | 0.078919 |
| 100000 | 7:49.454265 | 7:36.097941 | 16:11.984410 | 0.363053 | 0.727779 | 0.902417 | 0.346637 | 1.036951 |
| 1000000 | -- | -- | -- | 4.852743 | 9.156494 | 14.213323 | 4.633675 | 13.360319 |
从测试数据对比来看，基数排序在最终的排序耗时上表现是最好的。
既然基数排序效果这么好，为什么没有其它的排序算法（比如快排）应用更广泛呢？我觉得应该是基数排序的使用范围有限，并不是所有的排序都能使用基数排序。能用于基数排序需要序列中的元素都是有基数的（整数和浮点数）。
转载请注明：禅思 » 常见排序算法的Python实现，及其复杂度和稳定性分析？
