排序算法大赏（未完待续）

一、前言

排序算法也是面试中常常提及的内容，问的最多的应该是快速排序、堆排序。这些排序算法很基础，但是如果平时不怎么写代码的话，面试的时候总会出现各种bug。虽然思想都知道，但是就是写不出来。本文打算对各种排序算法进行一个汇总，像插入排序、冒泡排序、选择排序等就简单的介绍，重点关注快速排序和堆排序。需要提到的一点就是：插入排序，冒泡排序，归并排序，计数排序都是稳定的排序，而其他排序则都是不稳定的。

二、简单排序

1）插入排序

插入排序是很基本的排序，特别是在数据基本有序的情况下，插入排序的性能很高，基本可以达到O(N）。当然其最坏情况和平均情况时间复杂度都是O(N^2)。代码如下：

void insert_sort(int x[], int n)
{
    int i, j;
    for (i=1; i<n; i++) {
        /*循环不变式：x[0...i-1]有序。每次迭代开始前，x[0...i-1]有序， 循环结束后i=n，x[0...n-1]有序*/
        int key = x[i];
        for (j=i; j>0 && x[j-1]>key; j--) {
            x[j] = x[j-1];
        }
        x[j] = key;
    }
}

2）选择排序

选择排序的思想就是第i次选取第i小的元素放在位置i。比如第1次就选择最小的元素放在位置0，第2次选择第二小的元素放在位置1。选择排序最好和最坏时间复杂度都为O(N^2)。代码如下：

void select_sort(int x[], int n)
{
    int i, j, min, tmp;
    for (i=0; i<n-1; i++) {
        min = i;
        for (j=i+1; j<n; j++) {
            if (x[j] < x[min])
                min = j;
        }
        if (min != i)
            tmp = x[i], x[i] = x[min], x[min] = tmp;//交换x[i]和x[min]
    }
}

循环不变式：在外层循环执行前，x[0...i-1]包含a中最小的i个数，且有序。

初始时，i=0，x[0...-1]为空，显然成立。

每次执行完成后，x[0...i]包含x中最小的i+1个数，且有序。即第一次执行完成后，x[0...0]包含x最小的1个数，且有序。

循环结束后，i=n-1，则x[0...n-2]包含x最小的n-1个数，且已经有序。所以整个数组有序。

3）冒泡排序

冒泡排序时间复杂度跟选择排序相同。其思想就是进行n-1趟排序，每次都是把最小的数上浮，像鱼冒泡一样。最坏情况为O(N^2)。代码如下：

void bubble_sort(int x[], int n)
{
    int tmp;
    for (int i=0; i<n; i++) {
        for (int j = n-1; j>=i+1; j--) {
            if (x[j] < x[j-1])
                tmp = x[j], x[j] = x[j-1], x[j-1] = tmp;
        }   
    }   
}

循环不变式：在循环开始迭代前，子数组x[0...i-1]包含了数组x[0..n-1]的i-1个最小值，且是排好序的。

对冒泡排序的一个改进就是在每趟排序时判断是否发生交换，如果一次交换都没有发生，则数组已经有序，可以不用继续剩下的趟数直接退出。改进后代码如下：

void bubble_sort_better(int x[], int n)
{
    int tmp;
    for (int i=0; i<n; i++) {
        int sorted = 1;
        for (int j = n-1; j>=i+1; j--) {
            if (x[j] < x[j-1]) {
                tmp = x[j], x[j] = x[j-1], x[j-1] = tmp;
                sorted = 0;
            }   
        }   
        if (sorted)
            return ;
    }   
}

4）计数排序

假定数组为A[0...n-1],数组中存在重复数字，数组中最大数字为k，建立两个辅助数组B和C，B用于存储排序后的结果，C用于存储临时值。时间复杂度为O(N)，适用于数字范围较小的数组。具体见代码：

const int N = 5; //数字个数
int b[N+1];
void count_sort(int a[], int n, int k) //k为数组最大数字
{
    int c[k+1];  //辅助数组
    for (int i=0; i<=k; i++)
        c[i] = 0;
    for (int j=0; j<n; j++)
        c[a[j]] = c[a[j]] + 1; //C[i]包含等于i的元素个数

    for (int i=1; i<=k; i++)
        c[i] = c[i] + c[i-1];  //C[i]包含小于等于i的元素个数

    for (int j=n-1; j>=0; j--) {
        b[c[a[j]]] = a[j]; //结果存在B[1...N]中
        c[a[j]] = c[a[j]] - 1;
    }
}

5）归并排序

归并排序通过分治算法，先排序好两个子数组，然后将两个子数组归并。时间复杂度为O(NlgN）。代码如下：

/*归并排序代码*/
void merge_sort(int a[], int p, int r) 
{
	if (p < r) {
		int q = p+(r-p)/2;
		merge_sort(a, p, q);
		merge_sort(a, q + 1, r);
		merge(a, p, q, r);
	}
}

void merge(int a[], int start, int mid, int end) 
{
	int n1 = mid - start + 1;
	int n2 = end - mid;
	int left[n1], right[n2];
	int i, j;
	for (i = 0; i < n1; i++) /* left holds a[start..mid] */
		left[i] = a[start + i];
	for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
		right[j] = a[mid + 1 + j];
	i = j = 0;
	int k = start;
	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++];
}

三、堆排序