扩展： 如果代码中的给数组 b[] 赋值语句 for (j=n-1; j>=0; j--) 改为 for(j=0; j<=n-1; j++)，该代码仍然正确，只是排序不再稳定。
6.归并排序归并排序通过分治算法，先排序好两个子数组，然后将两个子数组归并。时间复杂度为 O(NlgN）。代码如下：
/* * 归并排序-递归 * */ void mergeSort(int a[], int l, int u) { if (l < u) { int m = l + (u-l)/2; mergeSort(a, l, m); mergeSort(a, m + 1, u); merge(a, l, m, u); } }/**
归并排序合并函数
*/
void merge(int a[], int l, int m, int u)
{
int n1 = m - l + 1;
int n2 = u - m;
int left[n1], right[n2];
int i, j;
for (i = 0; i < n1; i++) /* left holds a[l..m] */
left[i] = a[l + i];
for (j = 0; j < n2; j++) /* right holds a[m+1..u] */
right[j] = a[m + 1 + j];
i = j = 0;
int k = l;
while (i < n1 && j < n2) {
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
}
while (i < n1) /* left[] is not exhausted /
a[k++] = left[i++];
while (j < n2) / right[] is not exhausted */
a[k++] = right[j++];
}
复制代码
扩展：归并排序的非递归实现怎么做？
归并排序的非递归实现其实是最自然的方式，先两两合并，而后再四四合并等，就是从底向上的一个过程。代码如下：
/** * 归并排序-非递归 */ void mergeSortIter(int a[], int n) { int i, s=2; while (s <= n) { i = 0; while (i+s <= n){ merge(a, i, i+s/2-1, i+s-1); i += s; } //处理末尾残余部分 merge(a, i, i+s/2-1, n-1); s*=2; } //最后再从头到尾处理一遍 merge(a, 0, s/2-1, n-1);}
复制代码
基数排序的思想是对数字每一位分别排序（注意这里必须是稳定排序，比如计数排序等，否则会导致结果错误），最后得到整体排序。假定对 N 个数字进行排序，如果数字有 d 位，每一位可能的最大值为 K，则每一位的稳定排序需要 O(N+K) 时间，总的需要 O(d(N+K)) 时间，当 d 为常数，K=O(N) 时，总的时间复杂度为O(N)。
而桶排序则是在输入符合均匀分布时，可以以线性时间运行，桶排序的思想是把区间 [0，1) 划分成 N 个相同大小的子区间，将 N 个输入均匀分布到各个桶中，然后对各个桶的链表使用插入排序，最终依次列出所有桶的元素。
这两种排序使用场景有限，代码就略过了，更详细可以参考《算法导论》的第8章。
数据结构和算法面试题系列—排序算法之快速排序 0.概述快速排序也是基于分治模式，类似归并排序那样，不同的是快速排序划分最后不需要merge。对一个数组 A[p..r] 进行快速排序分为三个步骤：
划分： 数组 A[p...r] 被划分为两个子数组 A[p...q-1] 和 A[q+1...r]，使得 A[p...q-1] 中每个元素都小于等于 A[q]，而 A[q+1...r] 每个元素都大于 A[q]。划分流程见下图。
解决： 通过递归调用快速排序，对子数组分别排序即可。
合并：因为两个子数组都已经排好序了，且已经有大小关系了，不需要做任何操作。