45. 盘点那些必问的数据结构算法题之基础排序算法
盘点那些必问的数据结构算法题之基础排序算法0 概述排序算法也是面试中常常提及的内容，问的最多的应该是快速排序、堆排序。这些排序算法很基础，但是如果平时不怎么写代码的话，面试的时候总会出现各种bug。
虽然思想都知道，但是就是写不出来。**本文打算对各种排序算法进行一个汇总，包括插入排序、冒泡排序、选择排序、计数排序、归并排序，基数排序、桶排序、快速排序等。**快速排序比较重要，会单独写一篇，而堆排序见本系列的二叉堆那篇文章即可。
需要提到的一点就是：插入排序，冒泡排序，归并排序，计数排序都是稳定的排序，而其他排序则是不稳定的。
本文代码：https://github.com/shishujuan/dsalg/tree/master/code/alg/sort
1 插入排序插入排序是很基本的排序，特别是在数据基本有序的情况下，插入排序的性能很高，最好情况可以达到O(N)，其最坏情况和平均情况时间复杂度都是 O(N^2)。代码如下：
代码语言：javascript代码运行次数：0运行复制/**
* 插入排序
*/
void insertSort(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
/*
* 循环不变式：a[0...i-1]有序。每次迭代开始前，a[0...i-1]有序，
* 循环结束后i=n，a[0...n-1]有序
* */
int key = a[i];
for (j = i; j > 0 && a[j-1] > key; j--) {
a[j] = a[j-1];
}
a[j] = key;
}
}2 希尔排序希尔排序内部调用插入排序来实现，通过对 N/2，N/4…1阶分别排序，最后得到整体的有序。
代码语言：javascript代码运行次数：0运行复制/**
* 希尔排序
*/
void shellSort(int a[], int n)
{
int gap;
for (gap = n/2; gap > 0; gap /= 2) {
int i;
for (i = gap; i < n; i++) {
int key = a[i], j;
for (j = i; j >= gap && key < a[j-gap]; j -= gap) {
a[j] = a[j-gap];
}
a[j] = key;
}
}
}3 选择排序选择排序的思想就是第i次选取第i小的元素放在位置i。比如第1次就选择最小的元素放在位置0，第2次选择第二小的元素放在位置1。
选择排序最好和最坏时间复杂度都为 O(N^2)。
代码如下：
代码语言：javascript代码运行次数：0运行复制/**
* 选择排序
*/
void selectSort(int a[], int n)
{
int i, j, min, tmp;
for (i = 0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++) {
if (a[j] < a[min])
min = j;
}
if (min != i)
tmp = a[i], a[i] = a[min], a[min] = tmp; //交换a[i]和a[min]
}
}循环不变式：在外层循环执行前，a[0…i-1]包含 a 中最小的 i 个数，且有序。
初始时，i=0，a[0…-1] 为空，显然成立。每次执行完成后，a[0…i] 包含 a 中最小的 i+1 个数，且有序。即第一次执行完成后，a[0…0] 包含 a 最小的 1 个数，且有序。循环结束后，i=n-1，则 a[0…n-2]包含 a 最小的 n-1 个数，且已经有序。所以整个数组有序。4 冒泡排序冒泡排序时间复杂度跟选择排序相同。其思想就是进行 n-1 趟排序，每次都是把最小的数上浮，像鱼冒泡一样。最坏情况为 O(N^2)。代码如下：
代码语言：javascript代码运行次数：0运行复制/**
* 冒泡排序-经典版
*/
void bubbleSort(int a[], int n)
{
int i, j, tmp;
for (i = 0; i < n; i++) {
for (j = n-1; j >= i+1; j--) {
if (a[j] < a[j-1]){
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
}循环不变式：在循环开始迭代前，子数组 a[0…i-1] 包含了数组 a[0…n-1] 的 i-1 个最小值，且是排好序的。
对冒泡排序的一个改进就是在每趟排序时判断是否发生交换，如果一次交换都没有发生，则数组已经有序，可以不用继续剩下的趟数直接退出。改进后代码如下：
代码语言：javascript代码运行次数：0运行复制/**
* 冒泡排序-优化版
*/
void betterBubbleSort(int a[], int n)
{
int tmp, i, j;
for (i = 0; i < n; i++) {
int sorted = 1;
for (j = n-1; j >= i+1; j--) {
if (a[j] < a[j-1]) {
tmp = a[j], a[j] = a[j-1], a[j-1] = tmp;
sorted = 0;
}
}
if (sorted)
return ;
}
}5 计数排序假定数组为 a[0…n-1] ，数组中存在重复数字，数组中最大数字为k，建立两个辅助数组 b[] 和 c[]，b[] 用于存储排序后的结果，c[] 用于存储临时值。时间复杂度为 O(N)，适用于数字范围较小的数组。
计数排序原理如上图所示，代码如下：
代码语言：javascript代码运行次数：0运行复制/**
* 计数排序
*/
void countingSort(int a[], int n)
{
int i, j;
int *b = (int *)malloc(sizeof(int) * n);
int k = maxOfIntArray(a, n); // 求数组最大元素
int *c = (int *)malloc(sizeof(int) * (k+1)); //辅助数组
for (i = 0; i <= k; i++)
c[i] = 0;
for (j = 0; j < n; j++)
c[a[j]] = c[a[j]] + 1; //c[i]包含等于i的元素个数
for (i = 1; i <= k; i++)
c[i] = c[i] + c[i-1]; //c[i]包含小于等于i的元素个数
for (j = n-1; j >= 0; j--) { // 赋值语句
b[c[a[j]]-1] = a[j]; //结果存在b[0...n-1]中
c[a[j]] = c[a[j]] - 1;
}
/*方便测试代码，这一步赋值不是必须的*/
for (i = 0; i < n; i++) {
a[i] = b[i];
}
free(b);
free(c);
}扩展：如果代码中的给数组 b[] 赋值语句 for (j=n-1; j>=0; j–) 改为 for(j=0; j<=n-1; j++)，该代码仍然正确，只是排序不再稳定。
6 归并排序归并排序通过分治算法，先排序好两个子数组，然后将两个子数组归并。时间复杂度为 O(NlgN）。
代码如下：
代码语言：javascript代码运行次数：0运行复制/*
* 归并排序-递归
* */
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++];
}扩展：归并排序的非递归实现怎么做？
归并排序的非递归实现其实是最自然的方式，先两两合并，而后再四四合并等，就是从底向上的一个过程。
代码如下：
代码语言：javascript代码运行次数：0运行复制/**
* 归并排序-非递归
*/
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);
}7 基数排序、桶排序基数排序的思想是对数字每一位分别排序（注意这里必须是稳定排序，比如计数排序等，否则会导致结果错误），最后得到整体排序。
假定对 N 个数字进行排序，如果数字有 d 位，每一位可能的最大值为 K，则每一位的稳定排序需要 O(N+K) 时间，总的需要 O(d(N+K)) 时间，当 d 为常数，K=O(N) 时，总的时间复杂度为O(N)。
而桶排序则是在输入符合均匀分布时，可以以线性时间运行，桶排序的思想是把区间 [0，1) 划分成 N 个相同大小的子区间，将 N 个输入均匀分布到各个桶中，然后对各个桶的链表使用插入排序，最终依次列出所有桶的元素。
这两种排序使用场景有限，代码就略过了，更详细可以参考《算法导论》的第8章。
参考资料 《算法导论》
https://www.cnblogs.com/liushang0419/archive/2011/09/19/2181476.html