排序（二）

希尔排序（shell sort）

希尔排序是基于插入排序的基础上进行进一步的优化。
不过首先，我们要先解释一下为什么插入排序比较快。插入排序之所以快是因为它能适可而止，即在a[j] > a[j-1]时，不像冒泡与选择那样，每次都要重排一遍。

下面是希尔排序的写法：

    int gap = 1;
    while (gap < len/3)
        gap = gap*3 + 1;

    while (gap) {
        for (int i = gap; i < len; i++) {
            for (int j = i; j >= gap && a[j] < a[j-gap]; j -= gap) {
                int temp = a[j];
                a[j] = a[j-gap];
                a[j-gap] = temp;
            }   
        }   
        gap /= 3;
    }   

希尔排序的原理就是跳着找。而这样找之所以能比插入排序快的原因是：说不定有时候新加的数前面有许多比它大的数，一个一个找就会比较慢了，此时跳着找就可以避免许多次无用功的循环了。

归并排序 （merge sort）

归并排序的时间复杂度与快速排序一样。
而归并排序使用的原理是先将数组a从中间一个地方截开，使截出的两个部分个数相差不超过一，直到将整个数组a截成一个一个数，再进行排序、合并的循环。
而其排序时的原理是这样的：
比较两个未合并小数组（这两个小数组都已经分别排好序了）的首个，再把大的那个与另一数组中的第二个比较，以此类推。而每次都把小的那一个放入一个临时数组中去，最后把临时数组中的内容全都memcpy到原数组中。
其实现代码如下：

#include <cstring>

int merge_temp[maxn];

void merge(int a[], int start, int end)
{
    int middle = (start + end) / 2;
    int i = start, j = middle, k = start;
    while (i != middle && j != end) {
        merge_temp[k++] = a[i] < a[j] ? a[i++] : a[j++];
    }

    for (int m = j; m < end; m++, k++) {
        merge_temp[k] = a[m];
    }   
    for (int m = i; m < middle; m++, k++) {
        merge_temp[k] = a[m];
    }   
    memcpy(&a[start], &merge_temp[start], sizeof(int)*(end - start));
}

void merge_sort(int a[], int start, int end)
{
    if (start + 1 == end)
        return;

    int middle = (start + end)/2;
    merge_sort(a, start, middle);
    merge_sort(a, middle, end);
    merge(a, start, end);
}

不过，这个归并排序是有一点缺陷的。因为它要使用一个临时数组，而在很多时候，内存容量是有限的，所以给的数不能太多，而数少的话，那些简单的冒泡选择排序也能实现（并不会超时）。所以归并排序适用于数组中数的数量中等时使用。

快速排序 （quick sort）

快速排序的原理是先在数组中找一个基准数，再把数组分为比基准数大的数与比基准数小的数两个部分，再对这两个数组分别进行以上操作。而快速排序唯一的问题就在于如何找出一个很标准的基准数，但是并没有一个固定的方法可以找到，所以笔者就每次都以最后一个为基准数了。
其实现代码如下：

void quick_sort(int a[], int s, int e)
{
    if (s + 1 == e)
        return;

//  printf("s: %d, e: %d\n", s, e);
    int middle = s;
    for (int i = s; i < e; i++) {
        if (a[i] <= a[e-1]) {
            if (middle != i) {
                int temp = a[middle];
                a[middle] = a[i];
                a[i] = temp;
            }
//          printf("i: %d, ini: %d, a[i]: %d, a[ini]: %d\n", i, middle, a[i], a[initial]);
            middle++;
        }
    }

    if (middle == e) {
        quick_sort(a, s, e-1);
    } else {
        quick_sort(a, middle, e);
        quick_sort(a, s, middle);
    }
}

void sort_data(int a[], int len)
{
    quick_sort(a, 0, len);
}

计数排序（counting sort）
计数排序是所有排序中最快的，因为它只要把整个数组浏览几遍就可以排好序了。
计数排序的原理是把同一类的数放在一起。举一个例子，一道题要求输入-500000~500000 中的数，那么可以把所有-500000放在一起，所有-499999放在一起，以此类推。但是要是范围太大了，计数排序就没有任何优势了。
其代码如下：

#include <cstring>

int counting[1000001];

void sort_data(int a[], int len)
{
    memset(counting, 0, sizeof(counting));
    for (int i = 0; i < len; i++) {
        counting[a[i]+500000]++;
    }
    int j = 0;
    for (int i = 0; i < 1000001; i++) {
        while (counting[i] != 0) {
            a[j] = i - 500000;
            j++;
            counting[i]--;
        }
    }
}