前言
此为知乎之前文章的重置版，整理和消除了部分错误，适合收藏用。
本文总结了常用的全部排序算法，内容包括：
此文干货颇多，烦请收藏后慢慢研读。
面试知识点复习手册
此文属于知识点复习手册专栏内容，你还可以通过以下两种途径查看全复习手册文章导航：
-----正文开始-----算法性能分析
图中纠正：归并排序空间复杂度应该是O(n)，快排是O(logn)-O(n)
稳定性定义：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成r[j]>=r[j+1]，则两个相等的记录就会交换位置，从而变成不稳定的算法。
再如，快速排序原本是不稳定的排序方法，但若待排序记录中只有一组具有相同关键码的记录，而选择的轴值恰好是这组相同关键码中的一个，此时的快速排序就是稳定的。
只需记住一句话（快些选一堆美女一起玩儿）是不稳定的，其他都是稳定的。
补充性能图：
不同情况下的合适排序方法
初始数据越无序，快速排序越好。
已经基本有序时，用直接插入排序最快。
在随机情况下，快速排序是最佳选择。
既要节省空间，又要有较快的排序速度，堆排序是最佳选择，其不足之处是建堆时需要消耗较多时间。
若希望排序是稳定的，且有较快的排序速度，则可选用2路归并排序java 排序算法总结，其缺点需要较大的辅助空间分配。
算法实现基于比较的排序算法冒泡排序
思路：
冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
步骤：
:
def bubble_sort(array):
n = len(array)
for i in range(n): # i从0到n
for j in range(1, n-i): # 1开始，即j-1=0开始
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
return array
#优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。
#用一个标记记录这个状态即可。
def bubble_sort2(ary):
n = len(ary)
for i in range(n):
flag = 1 #标记
for j in range(1,n-i):
if ary[j-1] > ary[j] :
ary[j-1],ary[j] = ary[j],ary[j-1]
flag = 0
if flag : #全排好序了，直接跳出
break
return ary
#优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序了。
# 因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。
def bubble_sort3(ary):
n = len(ary)
k = n #k为循环的范围，初始值n
for i in range(n):
flag = 1
for j in range(1,k): #只遍历到最后交换的位置即可
if ary[j-1] > ary[j] :
ary[j-1],ary[j] = ary[j],ary[j-1]
k = j #记录最后交换的位置
flag = 0
if flag :
break
return ary
Java:
public void bubble_sort(int [] a) {
int n = a.length;
for(int i=0;i-1;j--) {
if (a[j] > num) {
a[j+1] = a[j];
index = j;
}
else {
a[index] = num;
break;
}
}
}
}
}
希尔排序（递减增量排序算法，实质是分组插入排序）
思路：
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
例如，假设有这样一组数，
[ 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步长进行排序（此时就是简单的插入排序了）。
具体实现：外面套一个gap，while内做插入排序，并且将gap不断除2，直到小于0出循环
：
def shell_sort(ary):
n = len(ary)
gap = round(n/2) # 初始步长 , 用round取整(注意0.5向下取)
while gap > 0 :
for i in range(gap,n): # 每一列进行插入排序 , 从gap 到 n-1
temp = ary[i]
index = i
while ( index >= gap and ary[index-gap] > temp ): # 插入排序
ary[index] = ary[index-gap]
index = index - gap
ary[index] = temp
gap = round(gap/2) # 重新设置步长
return ary
Java：
public void shell_sort(int [] a) {
int n = a.length;
int gap = n / 2;
while (gap > 0) {
for (int i=gap;i=gap && a[j-gap] > temp) {
a[j] = a[j-gap];
j = j - gap;
}
a[j] = temp;
}
gap = gap / 2;
}
}
归并排序(递归合并)
思路：拆拆拆到单个数字，合并合并合并
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的java 排序算法总结 排序算法最强总结及其代码实现（Python/Java），那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。
：
<p><pre>def merge_sort(array): # 递归
if len(array)