几种排序算法的收集

归并排序

按照分治三步法来理解，记住这三句话即可：
划分问题：把序列分成元素个数尽量相等的两半。
递归求解：把两半元素分别排序。
合并问题：把两个有序表合并成一个。
ok，接下来直接看代码就行，假设是一个从0开始的N个元素的数组:mergeSort(A,0,N,T);

void mergeSort(int *A, int x, int y, int *T) {
    if (y - x <= 1)
        return;
    int m = (x + y) / 2;
    int p = x, q = m, i = x;
    mergeSort(A, x, m, T);
    mergeSort(A, m, y, T);

    while (p < m || q < y) {
        if (q >= y || (p < m && A[p] <= A[q]))
            T[i++] = A[p++];
        else
            T[i++] = A[q++];
    }
    for (i = x; i < y; ++i)
        A[i] = T[i];
}

这里主要但凡有一个数组非空则需继续合并，里面的if稍要思考。若第2个序列为空，则此时第1个序列必然非空，复制A[p]。否则，第2个序列非空，当且仅当第1个序列也非空，且A[p]<=A[q]时，才复制A[p]。
这里提一个知识:利用归并排序求逆序数.假设已经将[l,m)和[m,r)排序好,对于当前位置T[i],假设是要插入右边的A[q],那么可知,[l,m)中[l,p-1]已然插入,是因为A[p]>A[q],导致现在要插入A[q],其实[p,m)就是左边数组中大于A[q]的数字了.所以:
将T[i++]=A[q++]; 修改(添加)成:T[i++]=A[q++],ans+=(m-p)即可.最后的ans即为逆序数.

快速排序

分治法三步：
划分问题：把数组各个元素重排后分成左右两部分，使得左边的任意元素都<=右边的任意元素。
递归求解：把左右两部分分别排序。
合并问题：不用合并，因为此时数组已经完全有序。
这里取的是中间的值，于是也无所谓”复位”一说,但是这里排序的是闭区间。

void quickSort(int *A, int L, int R) {
    int i = L, j = R;
    int mid = A[(i + j) / 2];
    while (i <= j) {
        while (A[i] < mid) ++i;
        while (A[j] > mid) --j;
        if (i <= j) {
            swap(A[i], A[j]);
            ++i;
            --j;
        }
    }
    if(i < R) quickSort(A, i, R);
    if(L < j) quickSort(A, L, j);
}

冒泡排序

void bubbleSort(int *A, int len) {
    for (int i = 0; i < len - 1; ++i)
        for (int j = 0; j < len - 1 - i; ++j)
            if (A[j] > A[j + 1])
                swap(A[j], A[j + 1]);
}

冒泡排序有常见2种优化：1种是在每一轮检测有无冒泡，无则已经有序，不再排序。1种是记录每次进行交换的最后一个位置，那么这个位置之后的数据已经沉底有序，不需再进行检索，可得：

void bubbleSort2(int *A, int len) {
    int k = len - 1, pos = 0;
    for (int i = 0; i < len - 1; ++i) {
        int changed = 0;
        for (int j = 0; j < k; ++j) {
            if (A[j] > A[j + 1]) {
                swap(A[j], A[j + 1]);
                changed = 1;
                pos = j;
            }
        }
        k = pos;
        if (!changed)
            break;
    }
}

插入排序

void insertSort(int *A, int len) {
    for (int i = 1; i < len; ++i) {
        if (A[i] >= A[i - 1])
            continue;
        int idx = i, val = A[i];
        while (idx >= 1) {
            if (val < A[idx - 1])
                A[idx] = A[idx - 1];
            else
                break;
            --idx;
        }
        A[idx] = val;
    }
}

希尔排序

希尔排序不稳定，时间复杂度约O(n^3)，步骤是：
按增量dis分成子序列；
对子序列进行直接插入排序；
缩小增量dis，重复以上步骤，直至dis=1；

void shellSort(int *A, int n) {
    int dis = n / 2;
    while (dis >= 1) {
        for (int i = dis; i < n; ++i) {
            int x = A[i];
            int j;
            for (j = i - dis; j >= 0 && x < A[j]; j -= dis)
                A[j + dis] = A[j];
            A[j + dis] = x;
        }
        dis /= 2;
    }
}

参考书目：
算法竞赛入门2 刘汝佳