归并排序
按照分治三步法来理解，记住这三句话即可：
划分问题：把序列分成元素个数尽量相等的两半。
递归求解：把两半元素分别排序。
合并问题：把两个有序表合并成一个。
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 刘汝佳
