内部排序是指待排序列完全位于内存中的排序过程，适合内存充足，能够一次性加载整个序列的情况，与此对应的还有外部排序。本文将详细介绍几种经典非线性内部排序算法的原理和实现，并分析各自的稳定性和时空性能。
排序算法的稳定性
采用何种排序算法，除了考虑数据规模和时空复杂度，特定场景下，稳定性也常常成为重要指标。我们称，满足以下特征的排序算法具有稳定性：使用某排序算法对待排序列排序，假设序列中有两个元素 e1 和 e2，e1.key = e2.key 且 e1 位于 e2 之前，使用该排序算法后，e1 仍处于 e2 之前。
既然 e1.key = e2.key，那么最终谁在前面又有什么影响呢？大多数情况下确实没有影响，但如果对复杂对象的多个属性排序，且下一次排序要保持上一次的某些局部相邻顺序，就要使用稳定的排序算法。例如要对商品对象按销量排序，如果销量相同就按价格排序。我们可以首先按价格排序，随后使用稳定的算法对销量排序。当然你也可以先按销量排序，随后遍历序列，在每个销量相同的区间里分别按价格排序，不过这样实现相对复杂，也不适合价格本身有序的情况。
快速排序
之所以首先介绍快速排序，一来因为它的平均时间复杂度为 O(nlogn)，空间复杂度为 O(logn)，在所有内部排序算法中综合性能最优，二来其主要思想是上一节介绍的 分治与递归，可当作递归的应用讲解。
基本思想
回顾能用递归解决的问题必须满足的三个条件：首先，原问题能够分解为几个规模较小的子问题。其次，原问题和子问题是同一问题。第三，存在终止条件。具体到排序，试想这样的操作：选定待排序列中任一元素作为分界点，将小于分界点的元素都放到其左边，大于分界点的元素都放到其右边，问题便转换为对分界点两侧的序列排序。分好类后，对于每个子序列，仍可使用上面的方法排序，即从原问题到子问题，规模变小，解决方法相同。当子序列仅有一个元素时，无需排序，这便是终止条件。可见，排序问题可以用递归解决。
现在寻找递推公式，假如要对数组下标从 p 到 r 之间的元素由小到大排序，选择在此之间的任意元素作为分界点 pivot，遍历待排序列，将小于 pivot 的元素放到其左边，大于 pivot 的元素放到其右边，下面是一个示例
pivot
↓
[8][10][2][3][6][1][5]
p r
分 |
区 ↓
[2][3][1][5][6][8][10]
p q r记对下标从 p 到 r 之间的序列排序的过程为 f(p, r)，q 是分区结束后 pivot 的数组下标，则对下标从 p 到 q-1 之间序列排序的过程为 f(p, q-1)，对下标从 q+1 到 r 之间序列排序的过程为 f(q+1, r)，要使整个序列有序，只要对两个子序列分别排序即可，所以 f(p, r) = f(p, q-1) and f(q+1, r)。
当子序列仅有一个元素，即 p >= r 时，排序结束，加上 > 的原因将在后面说明。下面是递归函数的实现代码
// 分区函数
int partition(int[] a, int p, int r) {
// 选择任意元素作为分区点 pivot，对 a 分区，
//+ 使 pivot 左边都小于它，右边都大于它，
//+ 最后返回分区结束后 pivot 的下标
// ...
}
void quickSort(int[] a, int p, int r) {
if (p >= r) return;
int q = partition(a, p, r);
quickSort(a, p, q-1);
quickSort(a, q+1, r);
}现在考虑如何高效实现 partition 函数，基本想法是开辟两个新数组 b 和 c，将小于 pivot 的元素拷贝到 b，大于 pivot 的元素拷贝到 c，最后再将 b，c 拷贝回 a。但这样实现的空间复杂度是 O(2n)，能否将其降到 O(1) 呢？考虑这样的做法：选定最后一个元素 a[r] 为 pivot，用 i 将 a[p, r-1] 分成两部分，记 a[p, i-1] 为 已处理区间，a[i, r-1] 为未处理区间。起初 i=p，遍历未处理区间，每次从中取一个元素 a[j]，若小于 pivot，则将其加入已处理区间末尾，即 a[i] 位置，此时已处理区间增加一个元素，i++。最终，i 前面都比 pivot 大，将 pivot 放到 i 位置，返回 i。下面是完整示例
p r
ij pivot
6 11 3 9 8 6<8，将 6 加入已处理序列，i 后移。继续遍历未处理序列，j 后移
ij
6 11 3 9 8 11>8，继续遍历未处理序列，j 后移
i j
6 11 3 9 8 3<8，将 3 加入已处理序列，i 后移。继续遍历未处理序列，j 后移
i j
6 3 11 9 8 9>8，未处理序列遍历完毕
i j
6 3 8 9 11 交换 8 和 11，将 pivot 移动到已处理序列末尾我们知道往数组插入元素的平均复杂度是 O(n)，那么整个 partition 函数的时间复杂度将是 O(n^2)，显然是可不取的。在 操作数组的几个技巧 中我们提到，如果仅将数组当作数据集合使用，无需考虑元素顺序，那么将元素插入到第 k 个位置的操作可简化为：将第 k 个位置的元素插入到数组尾，将新元素放到第 k 个位置上，不做数据搬移，时间复杂度为 O(1)。
此处，因为 a[i] 和 a[j] 都还处于未处理序列，即大于 pivot 的区间，而大于 pivot 的元素顺序我们并不关心，所以要将 a[j] 插入到 a[i] 的位置上，只需将两者交换，这样，插入便成为 O(1) 操作，整个 partition 函数的时间复杂度就是 O(n)。因为没有使用额外空间，空间复杂度是 O(1)。下面是 partition 的实现代码
void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int[] a, int p, int r) {
// 选取最后一个元素作为分界点
int pivot = a[r];
// 起初，整个序列都处于未处理区间
int i = p;
// 遍历未处理区间
for( int j=i; j<r; j++) {
// 如果元素比分界点小，则将其放到已处理序列末尾
if (a[j] < pivot)
// 已处理序列增加一个元素
swap(a, i++, j);
}
// a[i] 之前都小于 pivot，将 pivot 放到 i 位置即可
swap(a, i, r);
return i;
}考虑序列 1，2，3，4，5，第一次调用 partition 后将返回 4，所以会执行 quickSort(0，3)，quickSort(5, 4)，此时 5 > 4，这就是递归终止条件写成 p >= r 的原因。
稳定性
考虑序列 6，8，7，6，3，5，在 3 之前的元素都大于 5，而 3<5，所以第一个 6 要与 3 交换，这样序列中两个 6 的顺序就发生了变化，由此可见，快速排序是 不稳定 的排序算法。
性能分析
最好时间复杂度
快排所需时间等于对数组进行划分的时间加上两次递归调用的时间。假如每次 partition 都能把数组分成大小近似相等的两个子区间，那么递归的层数将到达最小，所花时间最少。记对 n 个元素进行快速排序的时间为 T(n)，那么对每个子区间排序的时间就是 T(n/2)，有 T(n) = n + 2 * T(n/2)，其中 n 为划分所花时间。当 n = 1 时无需排序，即 T(1) = C。假如整个过程进行了 k 次递归，有
$$ \begin{equation} \begin{aligned} T(n) &= n + 2 * T(\frac{n}{2})\\ &= 2n + 4 * T(\frac{n}{4})\\ &= 3n + 8 * T(\frac{n}{8})\\ &...\\ &= kn + 2^{k} * T(\frac{n}{2^{k}}) \end{aligned} \end{equation} $$
当 n/2^k = 1，即 k = logn 时，T(n) = nlogn + Cn。所以快速排序的最好时间复杂度是 O(nlogn)。
最坏时间复杂度
如果待排序列初始状态是逆序，每次递归前半部分没有元素，后半部分元素个数为整个序列长度减 1，所以总共要进行 n 层递归，每层递归中，划分操作的时间复杂度是 O(n)，所以最坏时间复杂度是 O(n^2)。
平均时间复杂度
记对 n 个数进行划分后，k-1 个数被划分到左边，k 可能是 1-n 之间的任意数字，且每种可能概率相等，都是 1/n。所以对 n 个数进行快速排序，其平均时间的递推公式如下，其中 Cn 是划分所用时间：
$$ T(n)=Cn+\frac{1}{n}\sum_{k=1}^n[T(k-1)+T(n-k)] $$
记 S(n-1) = T(0) + T(1) + ... + T(n-1)，有
$$ T(n)=Cn+\frac{2}{n}S(n-1) $$
移项得
$$ S(n-1)=\frac{n}{2}[T(n)-Cn] $$
$$ S(n-2)=\frac{n-1}{2}[T(n-1)-C(n-1)] $$
因为 T(0)=T(1)=1，所以
$$ T(n-1)=S(n-1)-S(n-2)=\frac{n}{2}[T(n)-Cn)]-\frac{n-1}{2}[T(n-1)-C(n-1)] $$
等号两边同时乘 2 并移项整理得
$$ nT(n)=(n+1)T(n-1)+2Cn-C $$
为了简化计算，去除最后的非决定项 -C，两边同时除以 n(n+1) 得
$$ \frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{2C}{n+1} $$
现在进行叠缩
$$ \frac{T(n-1)}{n}=\frac{T(n-2)}{n-1}+\frac{2C}{n}\\ \frac{T(n-2)}{n-1}=\frac{T(n-3)}{n-2}+\frac{2C}{n-1}\\ ...\\ \frac{T(2)}{3}=\frac{T(1)}{2}+\frac{2C}{3} $$
将以上叠缩式相加并约分整理得
$$ \frac{T(n)}{n+1}=\frac{T(1)}{2}+2C\sum_{i=3}^{n+1}\frac{1}{i} $$
上式的最后一项是调和级数的部分和，两边同时乘以 n+1 得
$$ T(n)=2C(n+1)[ln(n+1)+r-3]+\frac{n+1}{2}，r 为欧拉-马歇罗尼常数 $$
所以，快速排序的平均时间复杂度是 O(nlogn)。
空间复杂度
最坏情况下，快速排序要进行 n 层递归，空间复杂度 O(n)，最好和平均情况下要进行 logn 层递归，空间复杂度 O(logn)。
快速排序的优化
针对快排的优化主要从四个方面入手。第一，固定位置选取 pivot 容易导致分割不均，通常采用三数取中法。第二，对于重复元素过多的序列，可将所有与 pivot 相等的元素移到 pivot 两边，下次递归时忽略这些元素。第三，元素较少时采用插入排序。第四，将第二个递归改为循环，即尾递归优化，通常编译器会自动进行。
应用：寻找第 K 大数
有很多种做法，首先是直接排序，时间复杂度为 O(nlogn)。其次是循环 K 次，每次排除当前数组的最小值，时间复杂度 O(Kn)。更好的做法是利用快排的分区思想，例如数组 a[p,r]，每次选取 a[r] 作为 pivot 将数组分成三个区 a[p, pivot-1]，a[pivot] 和 a[pivot+1,r]。如果 pivot+1 = K，则 a[pivot] 就是第 K 大数。如果 pivot+1 < K，则结果在 a[pivot+1,r] 中，反之结果在 a[p, pivot-1] 中。假如 pivot 每次都能将数组平分，那么整个过程要遍历的元素个数为
$$ \begin{equation} \begin{aligned} T(n)&=n+\frac{n}{2}+\frac{n}{4}+...+\frac{n}{2^{k}}+1\\ &=n(1+\frac{1}{2}+\frac{1}{4}+...+\frac{1}{2^k})+1\\ &=n\frac{1-\frac{1}{2^{k+1}}}{1-\frac{1}{2}}+1\\ &=2n-\frac{n}{2^k}+1,\ 2^{k+1}=n\\ &=2n-1 \end{aligned} \end{equation} $$
所以时间复杂度为 O(n)，下面是示例代码
int kTh(int[] a, int p, int r, int k) {
int q = partition(a, p, r);
int cTh; // 保存 q 位置是第几大数
while ((cTh = q + 1 - p) != k) {
if (cTh > k) {
q = partition(a, p, q - 1);
} else {
q = partition(a, q + 1, r);
}
}
return a[q];
}递归实现更容易理解。
int kTh(int[] a, int p, int r, int k) {
int q = partition(a, p, r);
int cTh = q + 1 - p;
if (cTh == k)
return a[q];
else if (cTh > k)
return kTh(a, p, q - 1, k);
else
return kTh(a, q + 1, r, k - cTh);
}归并排序
归并排序与快速排序一样，也利用了分治思想，并且其最好最坏和平均时间复杂度都是 O(nlogn)，除此之外它还是稳定的排序算法，唯一缺点是空间复杂度为 O(n)。
基本思想
将待排序列从中间分成两部分，对它们分别排序，最后将排好序的两部分合并。下面是一个示例：
--- 11 8 3 9 7 1 2 5
↓ ↙ ↘
11 8 3 9 7 1 2 5
分 ↙ ↘ ↙ ↘
11 8 3 9 7 1 2 5
↑ ↙ ↘ ↙ ↘ ↙ ↘ ↙ ↘
--- 11 8 3 9 7 1 2 5
↓ ↘ ↙ ↘ ↙ ↘ ↙ ↘ ↙
8 11 3 9 1 7 2 5
合 ↘ ↙ ↘ ↙
3 8 9 11 1 2 5 7
↑ ↘ ↙
--- 1 2 3 5 7 8 9 11如上图所示，对于每个子序列我们仍然可以继续分割，直到子序列只有一个元素时，它肯定是有序的，随后将有序子序列逐层合并就能使整个序列有序。记为 p，r 间序列排序的过程为 mergeSort(p,r)，以 p，r 中点 q 将序列分成前后两部分，则对两部分分别排序的过程为 mergeSort(p,q) 及 mergeSort(q+1,r)，合并数组 a,b 的过程为 merge(a,b)，则有以下递推公式
mergeSort(p,r) = merge(mergeSort(p,q), mergeSort(q+1,r)), q=(p+r)/2递归终止条件为 p >= r，大于号在序列仅有 2 个元素时取到，不妨令 p=0，r=1，则 q = (p+r)/2 = 0，此时会执行 mergeSort(0, 0) 和 mergeSort(1, 0)，满足 p>=r。下面是实现代码
void mergeSort(int[] a, int p, int r) {
if (p >= r) return;
int q = (p+r)/2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, r, q);
}上述代码中 merge 函数的作用是合并原始序列 a[p,r] 的前后两部分，具体做法是开辟一个与待合并序列大小相等的新数组 tmp，随后设定两个指针 i 和 j 分别指向两个待合并序列的起始位置 p 和 q+1，比较 a[i] 和 a[j]，将较小者放入 tmp 末尾，同时相应指针后移。如果某个指针走至所在部分末尾，则将另一指针所在部分剩余元素全部插入 tmp 末尾，最后将 tmp 拷贝回数组 a。下面是实现代码
void merge(int[] a, int p, int r, int q) {
int[] tmp = new int[r-p+1];
int i = p;
int j = q+1;
int k = 0;
while (i<=q && j<=r)
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
while (i <= q)
tmp[k++] = a[i++];
while (j <= r)
tmp[k++] = a[j++];
for (k=0,; k<r-p+1; k++)
a[p+k] = tmp[k];
}稳定性
容易看出，归并排序的稳定性依赖于合并函数 merge，具体来说是函数的第 9 行 if (a[i] <= a[j])。上述代码实现的是从小到大排序，其中 a[i] 位于前半部分，a[j] 位于后半部分。根据语义，当 a[i]=a[j] 时，a[i] 会先于 a[j] 进入数组，这就决定了 a[i] 最终仍会位于 a[j] 之前，所以归并排序是 稳定 的排序算法。
性能分析
时间复杂度
记对含 n 个元素的序列排序所需时间为 T(n)，由于每次都是平分序列，所以 T(n) = 2*T(n/2) + n，其中 n 为合并所需时间，有以下递推公式
$$ \begin{equation} \begin{aligned} T(n) &=2*T(\frac{n}{2})+n\\ &=2*2*T(\frac{n}{4})+2n\\ &...\\ &=2^{k}*T(\frac{n}{2^{k}})+kn\\ \end{aligned} \end{equation} $$
假设整个排序过程需要 k 层递归，由于递归的终止条件是 T(1) = 1，可令 n/2^k = 1，即 k=logn，则
$$ T(n)=n+n*log_2n $$
所以，归并排序的时间复杂度是 O(nlogn)。需要注意的是，由于每次都是平分序列，无论初始状态如何，归并的时间都是相同的，即最好、最坏和平均时间复杂度都是 O(nlogn)。
空间复杂度
归并排序中的 merge 函数需要 O(n) 的额外空间，虽然整个排序过程要进行 logn 层递归，但上层 merge 执行时，下层 merge 已经将空间释放，又 O(logn) < O(n)，所以归并排序的空间复杂度是 O(n)。
插入排序
基本思想
往有序数组插入新元素，要求插入后数组仍然有序，做法是遍历数组，找到合适的位置后将后面所有元素搬移，最后将新元素插入到那个位置，插入排序便利用了该思想。
和快速排序的 partition 函数一样，插入排序也将数组分为 已排序 和 未排序 两个区间，起初已排序区间只有一个元素，即数组首元素。每次取未排序区间的第一个元素，在已排序区间中找到合适位置并插入，重复这个过程，直到未排序区间为空，算法结束。下面是一个示例
sorted | unsorted
4 | 5 6 1 3 2
4 5 | 6 1 3 2
4 5 6 | 1 3 2
1 4 5 6 | 3 2
1 3 4 5 6 | 2
1 2 3 4 5 6 |下面是实现代码
void insertionSort(int[] a) {
if (a.length<2) return;
for (int i = 1; i < a.length; i++) {
// 当前元素比已处理序列最大值都大，直接放末尾
if (a[i] >= a[i-1]) continue;
//保持未处理序列首元素，避免覆盖
int t = a[i];
// 记录插入位置，i 是未处理序列头，i-1 是已处理序列尾
int j = i-1;
// 逆序遍历已处理序列，寻找合适插入位置，并将之后的元素后移
for (; j>=0 && a[j]>t; j--)
a[j+1] = a[j];
// 插入到合适位置
a[j+1] = t;
}
}稳定性
上述代码内部 for 循环的终止条件 a[j] > t 决定，当元素相等时，后出现的元素不会插入到前面，所以插入排序是 稳定 的排序算法。
性能分析
最好时间复杂度
当元素本身有序且为正序时，插入排序无须移动元素，时间复杂度为 O(n)。
最坏时间复杂度
当元素逆序时，每次插入都要移动已处理序列的所有元素，时间复杂度为 O(n^2)。
平均时间复杂度
当 i<j 时，若 a[i]<=a[j]，则称 a[i] 与 a[j] 为一组有序元素对，有序度是数组中有序元素对的个数。逆序度的定义与有序度相反。对于完全有序的数组，称它的有序度为满有序度。对于含 n 个元素的数组，其满有序度为
$$ \begin{equation} \begin{aligned} FullOrderDegree &=(n-1) + (n-2) + ... + 1\\ &=\frac{n(n-1)}{2} \end{aligned} \end{equation} $$
满有序度=逆序度+有序度，排序就是增加有序度，减少逆序度的过程。插入排序包含两个操作，比较和移动，对于给定的初始序列，每次遍历已处理序列时，只有逆序才需要移动，每移动一个元素，逆序度都减 1，所以插入排序的移动次数等于初始序列的逆序度。
另一方面，插入排序本质是 n 次数组插入，数组插入的平均复杂度为 O(n)，所以插入排序的平均时间复杂度就为 O(n^2)。
空间复杂度
算法使用了常数级的额外空间，所以最好最坏和平均空间复杂度都为 O(1)。
插入排序的优化
折半插入排序
因为已处理序列是有序的，因此可使用折半查找的方法寻找插入位置，这样可将比较次数降低到 O(nlogn)。下面是示例代码
void insertSort(int[] a) {
if (a.length<2) return;
// 遍历未处理序列
for (int i=1; i<a.length; i++) {
// 未处理序列首元素大于已处理序列尾元素，直接插入到末尾
if (a[i] >= a[i-1]) continue;
// 记录未处理序列首元素，避免移动元素覆盖
int t = a[i];
int low = 0;
int high = i-1;
while (low <= high) {
/**
* 1.
* [low, high]
* mid
* 1.1 mid > t -> high = mid - 1, end, low/mid
* 1.2 mid = t -> low = mid + 1, end, low/mid, low is good
* 1.3 mid < t -> low = mid + 1, end, low
*
* 2.
* [low|high]
* mid
* 2.1 mid > t -> high = mid - 1, end, low/mid
* 2.2 mid = t -> low = mid + 1, end, low/mid, low is good
* 2.3 mid < t -> low = mid + 1, end, low
*/
int mid = (low+high)/2;
if (a[mid] > t)
high = mid-1;
else
low = mid + 1;
}
// 逆序遍历已处理序列，移动元素
for(int j=i-1; j>=low; j--)
a[j+1] = a[j];
// 插入到合适位置
a[low] = t;
}
}希尔排序
直接插入排序的移动次数等于初始序列的逆序度，如果数据规模较小且初始序列基本有序，比较和移动次数就会显著降低。基于以上两点 D.L.Shell 于 1959 年发明了希尔排序，其基本思想是：把记录下标按一定增量分组，对每组使用直接插入排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个文件恰被分成一组，再进行一次插入排序，整个序列便达到有序。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，都一步一步地对元素进行比较，移动，插入。比如 [ 5, 4, 3, 2, 1, 0 ] 这种倒序序列，数组末端的 0 要回到首位很是费劲，比较和移动均需 n-1 次。希尔排序采用跳跃式分组策略，通过某个增量将数组元素划分为若干组，分组进行插入排序。处理完所有组后，减小增量，继续按组进行插入排序，直至增量为 1。通过这种策略使得整个数组在初始阶段达到宏观基本有序，到增量为1时，只需微调即可。
目前尚未求得一个最好的增量序列，希尔的做法是 d1=n/2, d(i+1)=⌊di/2⌋，且最后一个增量为 1。在理解希尔排序时，我们倾向于逐组处理，但在代码实现中，不用处理完一组再回去处理下一组（这样还得加个 for 循环去处理分组）。比如 [ 5, 4, 3, 2, 1, 0 ] ，首次增量设 d1=length/2=3，将序列分成 3 组 [ 5, 2 ] [ 4, 1 ] [ 3, 0 ]，实现时不用循环按组处理，而是从第 d1 个元素开始逐个遍历，实现跨组处理。以下是示例代码
void shellSort(int[] a, int n) {
if (n < 2) return;
// 间距逐步减小，每组元素逐步增多，分组数逐步减少
for (int dk=n/2; dk>=1; dk/=2) {
// 逐个遍历，实现跨组处理
//+ 随着 i++，dk 分别是第一组，第二组，... ，第 dk 组未处理序列的第 一 个元素，
//+ 第一组，第二组，... ，第 dk 组未处理序列的第 二 个元素，
//+ ...
//+ 第一组，第二组，... ，第 dk 组未处理序列的第 n/dk 个元素。
for (int i=dk; i<a.length; i++) {
// 如果未处理序列开头比已处理序列最大值还大，直接放末尾
if (a[i] >= a[i-dk]) continue;
// 记录未处理组开头，避免覆盖
int t = a[i];
// 记录插入位置，i-dk 是已处理序列最后一个元素
int j = i-dk;
// 遍历已处理序列，将大元素后移
for(; j>=0 && t<a[j]; j-=dk)
a[j+dk] = a[j];
// 插入到合适位置
a[j+dk] = t;
}
}
}此外除了一次性移动所有元素，也可采用将待插入元素逐个与大于它的元素交换的方法，以下是示例代码
void shellSort(int[] a, int n) {
if (n < 2) return;
for (int dk=n/2; dk>0; dk/=2) {
for (int i=dk; i<a.length; i++) {
if (a[i] >= a[i-dk]) continue;
for (int j=i; j-dk>=0 && a[j]<a[j-dk]; j-=dk)
swap(a, j, j-dk);
}
}
}当相等元素被划分到不同组时，可能会改变它们的相对次序，所以希尔排序是 不稳定 的排序算法。下面的示例一目了然
3 2 2* 1 0 dk=5/2=2
^ ^ ^
0 1 2* 2 3
^ ^ ^
0 1 2* 2 3 dk=2/2=1希尔排序的空间复杂度为 O(1)，它的时间复杂度依赖于增量序列函数，这涉及到数学上尚未解决的难题，所以不便准确分析，当 n 在某个特定范围时，其时间复杂度约为 O(n^1.3)，最坏情况下时间复杂度为 O(n^2)。希尔排序是冲破 O(n^2) 的第一批算法之一。
选择排序
基本思想
与插入排序类似，选择排序也将数组分为已排序和未排序区间，不同的是，选择排序每次从未排序区间选择最小元素后缀至已排序区间。因为并不关心未排序区间第一个元素 p 和最小元素 min 的顺序，并且 p 将在下一步进入已排序区间，所以后缀 min 的操作可以转换为交换 p 和 min，下面是一个示例
sorted | unsorted
| 4 5 6 3 2 1 swap 4 and 1
1 | 5 6 3 2 4 swap 5 and 2
1 2 | 6 3 5 4 swap 6 and 3
1 2 3 | 6 5 4 swap 6 and 4
1 2 3 4 | 5 6 swap 5 and 5
1 2 3 4 5 | 6 swap 6 and 6
1 2 3 4 5 6 |下面是实现代码
int selectionSort(int[] a) {
for (int i=0; i<a.length; i++) {
int minIndex = i;
for(int j=i+1; j<a.length; j++)
if (a[j] < a[minIndex]) {
minIndex = j;
}
swap(a, i, minIndex);
}
}稳定性
考虑序列 5，6，5，2，9，第一次找到的最小元素是 2，要将其与第一个 5 交换，这样就改变了两个 5 的顺序，所以选择排序 不具有稳定性。
性能分析
时间复杂度
无论原始序列有序性如何，选择排序都要进行 n 次寻找最小值的操作，而寻找最小值的时间复杂度是 O(n)，所以选择排序的最好最坏和平均时间复杂度都是 O(n^2)。
空间复杂度
算法使用了常数级空间，所以空间复杂度为 O(1)。
冒泡排序
基本思想
同样将数组分为已就绪和未就绪区间，初始状态整个数组都未就绪。遍历未就绪区间，比较相邻元素，若不满足大小关系则交换，一次遍历会至少让一个元素移动到它应该在的位置，重复 n-1 次就完成了排序工作。下面是一次冒泡过程
从小到大排序，if(a[j] > a[j+1]) 交换
4 5 6 3 2 1 , 4<5 不交换
j
4 5 6 3 2 1 , 5<6 不交换
j
4 5 6 3 2 1 , 6>3 交换
j
4 5 3 6 2 1 , 6>2 交换
j
4 5 3 2 6 1 , 6>1 交换，结束
j
首次冒泡后，整个数组的最大值到达最终位置，下次冒泡，次大值将到达最终位置
还可以看出，若某次冒泡，如果未就绪序列有 m 个元素，则要进行 m-1 次比较某些情况下，排序操作不需要 n-1 次冒泡，因为如果某次冒泡没有发生数据交换，说明未就绪序列相邻元素全部满足大小关系，即未就绪序列实际上已经就绪，可停止后续冒泡，下面是示例代码
void bubbleSort(int[] a) {
for (int i=0; i<a.length-1; i++) {
boolean sorted = true;
for (int j=0; j<a.length-i-1; j++) {
if(a[j]>a[j+1]) {
swap(a, j, j+1);
sorted = false;
}
}
if(sorted) break;
}
}稳定性
冒泡排序只交换相邻元素，对于非相邻相等元素，最终会因逐个交换而相邻，因此只要保证相等元素不交换，就可保证排序的稳定性。换句话说，冒泡排序是 稳定 的排序算法。
性能分析
最好时间复杂度
当元素和待排顺序相同时，只需一次冒泡，所以最好时间复杂度为 O(n)。
最坏时间复杂度
当元素逆序是，要进行 n-1 次冒泡，所以最坏时间复杂度为 O(n^2)。
平均时间复杂度
冒泡排序的两个基本操作是比较和交换。每进行一次交换，序列的有序度就加 1，所以冒泡排序的交换次数等于原始序列的逆序度。
对于包含 n 个元素的数组，最坏情况逆序度为 n(n-1)/2，最好情况逆序度为 0，粗略取中间值 n(n-1)/4 作为平均逆序度，则冒泡排序的平均交换次数为 n(n-1)/4，比较次数显然大于交换次数，而最坏时间复杂度为 O(n2)，所以其平均时间复杂度为 O(n^2)。
空间复杂度
算法使用了常熟级额外空间，所以最好最坏和平均时间复杂度都是 O(1)。
堆排序
如果一棵二叉树的结点要么是叶子结点，要么该节点有两个子结点，那么这颗树就是满二叉树。完全二叉树是由满二叉树引申出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。也可以这样定义：设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大，第 h 层所有的结点都连续集中在最左边，这颗树就是完全二叉树。
堆 (Heap) 又被称为优先队列 (Priority Queue)。尽管名为优先队列，但它并不是队列。队列先进先出，而堆必须根据优先级取出元素。由完全二叉树 (Complete Binary Tree) 实现的堆称为二叉堆 (Binary Heap)。二叉堆是具有下列性质的完全二叉树：如果一颗完全二叉树每个节点的值都大于等于（小于等于）其左右孩子节点的值，则将这颗完全二叉树称为大顶堆或大根堆（小顶堆或小根堆）。堆的主要操作是添加最后一个节点和删除第一个节点，在插入或删除后，必须仍保持堆的性质: 1. 完全二叉树。2. 每个节点值都大于等于（小于等于）它的子节点。
插入新节点 new 时，将其放到最后一个节点之后，此时可能破坏堆的性质，要进行调整，具体操作为：将 new 与父节点比较，构建大根堆时，如果 new 节点比父节点大，那么交换两者。交换之后，继续与父节点比较，直到 new 节点不比父节点大，或者 new 节点成为根节点。下面是一次建立大根堆的过程
53
17 78
09 45 65 87
↑
32
53
17 78
↑
32 45 65 87
09
53
17 87
↑
32 45 65 78
09
53
↑
45 87
32 17 65 78
09
87
45 53
↑
32 17 65 78
09
87
45 78
32 17 65 53
09堆只能删除根节点。根节点删除后，会得到两棵子树，需要基于它们重构堆：让最后一个节点 last 成为根构成新二叉树，再将 last 节点不断和子节点比较，构建大根堆时，如果 last 节点比两个子节点中大的那个小，则与该子节点交换。继续比较，直到 last 不小于任一子节点，或成为叶节点时，堆重构完成。堆排序（Heap Sort）便是利用堆设计的排序算法。
基本思想
堆排序是一种树形选择排序，其基本思想是：将待排数组构建成大根堆，不断删除堆顶（最大值）直到堆中仅含一个元素，排序完成。以下是示例代码
// 不使用 a[0]，len 为无序区（堆）元素个数
void heapSort(int[] a, int len) {
// 仅含一个元素，无需排序
if (len < 2) return;
// 建立大根堆，堆顶 a[1] 是最大值
buildMaxHeap(a, len);
// 不断处理无序区（删除堆顶），直到仅含一个元素
while (len > 1) {
// 将最大值移到有序区，堆元素减一
swap(a, 1, len--);
// 从根开始往下调整，使之成为新堆
adjustDown(a, 1, len);
}
}
void buildMaxHeap(int[] a, int len) {
// len/2 是最大非叶节点（对应最后一颗子树）
//+ 建堆过程就是从最大非叶节点向上遍历，一直到根，
//+ 在此过程中，在每个非叶节点处向下调整，使对应子树满足堆的性质
for (int i=len/2; i>0; i--)
adjustDown(a, i, len);
}
// 将元素 k 向下调整，使子树成为堆，len 为堆中节点数
void adjustDown(int[] a, int k, int len) {
// 保存当前非叶节点
a[0] = a[k];
// 沿较大子节点向下筛选，从左子节点(2k)开始
for (int i=2*k; i<=len; i<<1) {
// 若右子节点大于左子节点，则 i 移动到右子节点
if (i < len && a[i]<a[i+1])
i++;
// 若当前非叶节点大于左右子树，则已经
//+ 满足堆的性质，无需继续向下调整
if (a[0] >= a[i])
break;
else {
// 否则将左右子节点的较大者上移
a[k] = a[i];
// 非叶节点下移
k = i;
}
}
// 将当前非叶节点放到合适位置，即第一次大于等于其子节点的位置，或最后一个叶子节点
a[k] = a[0];
}向下调整也可用递归实现，每次递归处理一层。
void adjustDown(int[] a, int k, int len) {
int i = 2 * k;
if (i > len)
return;
if (i + 1 <= len && a[i] < a[i + 1])
i++;
if (a[k] >= a[i])
return;
swap(a, k, i);
adjustDown(a, i, len);
}稳定性
在进行筛选时，有可能把后面相等的元素调整到前面，所以堆排序是 不稳定 的排序算法。下面是一个演示示例
待排序列
1 2 2*
建立大根堆
2
1 2*
删除堆顶，已排序列为 2
2*
1
删除堆顶，已排序列为 2* 2
1
堆中仅剩一个元素，排序结束，最终序列为
1 2* 2性能分析
时间复杂度
记树高为 h，则向下调整时间为 O(h)。建堆过程中每次向下调整时，大部分节点高度都较小，可证明建堆时间为 O(n)。如下是证明方法：假设完全二叉树有 n 个节点，则
$$ \sum_{i=0}^{h-1}2^i<n<=\sum_{i=0}^{h}2^i $$
解得 h≈logn。建堆调整时，最后一层每个父节点最多需下调 1 次，共 2^(h-1) 个节点。倒数第二层每个父节点最多需下调 2 次，共 2^(h-2) 个节点。依次类推，顶点最多需下调 h 次，共 1 个节点。所以总共需下调的次数为
$$ \begin{equation} \begin{aligned} T(n) &=1*2^{h-1}+2*2^{h-2}+...+h*2^0\\ \end{aligned} \end{equation} $$
可利用错位相减法计算 T(n)
$$ \begin{equation} \begin{aligned} 2T(n) &=1*2^{h}+2*2^{h-1}+3*2^{h-2}+...+\ \ h\ \ \ *\ \ \ \ \ 2^1\\ T(n) &=\ \ \ \quad\quad\quad1*2^{h-1}+2*2^{h-2}+...+(h-1)*2^1+h*2^0\\ T(n) &=1*2^h+1*2^{h-1}+1*2^{h-2}+...+\ \ 1\ \ \ \ *\ \ \ \ \ 2^1-h*2^0\\ &=\frac{2(1-2^h)}{1-2}-h\\ &=2^{h+1}-2-h,\ h=logn\\ &=2n-2-logn \end{aligned} \end{equation} $$
所以建立大根堆的时间复杂度是 O(n)。建堆完成后还要进行 n-1 次向下调整，每次调整时间复杂度都是 O(h)，所以堆排序的最好、最坏和平均时间复杂度都是 O(nlogn)。
空间复杂度
算法使用了常数级空间，所以堆排序的最好、最坏和平均空间复杂度都是 O(1)。
总结
类别 算法 时间复杂度 空间复杂度 稳定性
平均 最好 最坏
直接插入 O(n^2) O(n) O(n^2) O(1) 稳定
插入排序 折半插入 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n^1.3) O(n) O(n^2) O(1) 不稳定
选择排序 直接选择 O(n^2) O(n^2) O(n^2) O(1) 不稳定
树形选择 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
交换排序 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定对于稳定性，当排序过程中有非相邻元素交换，便会导致元素相对次序颠倒。希尔排序对序列分组，存在交叉移动。直接选择将未处理序列第一个元素与最小值交换，属于非相邻交换。堆排序采用树形结构，对子树向下调整，子树元素序号不一定连续。快速排序与直接选择类似。
几种简单排序中，直接插入的移动次数及冒泡排序的交换次数等于初始序列的逆序数，但冒泡排序赋值语句多于直接插入，而直接选择的交换次数与初始序列状态无关，但少于直接插入。因此，当数据规模较小时 （n <= 50），若序列基本有序则选择直接插入，若元素对象比较复杂，且不考虑稳定性，为减少移动开销，因使用简单选择。
当数据规模较大时，不考虑稳定性，优先选择优化后的快速排序。因为快速排序和堆排序时间复杂度一致，虽然后者空间复杂度更低，但其有如下缺点：第一，堆排序访问数据的方式不如快排。快排的划分函数对数据是顺序访问的，而堆排序对数据是跳跃式访问的，不利于 CPU 缓存。第二，对于同一组数据，堆排序交换次数多余快排。因为快速排序数据交换的次数小于等于原始序列的逆序数，而堆排序无论建堆还是删除堆顶都要向下调整，大多数情况下会导致逆序度增加。如果要选择稳定性算法，在内存充足的情况下，归并排序时间效率最高。
参考文献
- 排序算法的稳定性及其意义
- 如何证明快速排序法的平均复杂度为 O(nlogn)
- 递归算法的时间复杂度求解
- 调和级数
- 三种快速排序以及快速排序的优化
- 图解排序算法(二)之希尔排序
- 纸上谈兵: 堆 (heap)
- 动态图解十大经典排序算法
- 堆排序中建堆过程时间复杂度 O(n) 怎么来的
如有问题请在下方留言，文章转载请注明出处，详细交流请加下方群组！请大佬不要屏蔽文中广告，因为它将帮我分担服务器开支，如果能帮忙点击我将万分感谢。
可以 强大::quyin:witty::
哈哈，大佬来找错了