十大排序对比

in-place 占用常数内存，不占用额外内存
out-place 占用额外内存

1. 快速排序

• 算法描述：先找到⼀个枢纽；在原来的元素⾥根据这个枢纽划分 ：⽐这个枢纽⼩的元素排前⾯；⽐这个枢纽⼤的元素排后⾯；两部分数据依次递归排序下去直到最终有序。

• 模板：

void quick_sort(int q[], int l, int r)
{
	// 终止条件
    if (l >= r) return;  
    
    // 分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];  // 初始化
    while (i < j) {  // 遍历
        do ++i; while (q[i] < x);  // 遇到大于选取的数停止 
        do --j; while (q[j] > x);  // 遇到小于选取的数停止
        if (i < j) swap(q[i], q[j]);  // 判断 + 交换
    }
    
    // 递归处理子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 注意点：

1. i = l -1, j = r + 1, 是为了先 do 再 while，这样可以确保每次都能够推进两个指针向前或者向后；（如果先 while，当 = x 时，就会陷入无限循环）
2. x 可以任意取值，但最好取值为中点，这样可以提高可靠性；
3. swap 前一定要判断 if（i < j），两个指针交错后再交换会引起错误；
4. 递归时的分界时要注意，如果用 i-1 和 i 分界时，要让 x = q[l + r + 1 >> 1]，这里向上取整，避免 x = q[l] ，如果选取的点为 l，递归时可能为 quick_sort（q，l，l）而造成无限递归，同理用 j 和 j + 1分界时，不能选取点为 r；(无限递归的本质：递归时的范围可能再次出现[l，r])
5. 若要换成降序排列：只需替换 while（q[i] < x）与 while (q[i] > x);

2. 归并排序

• 算法描述

归并排序是⼀个稳定的排序算法，归并排序的时间复杂度任何情况下都是O(nlogn)，归并排序不是原地排序算法。
⽤两个游标 i 和 j，分别指向 A[p…q] 和 A[q+1…r] 的第⼀个元素。⽐较这两个元素 A[i] 和 A[j]，如果 A[i]<=A[j]，我们就把 A[i] 放⼊到临时数组 tmp，并且 i 后移⼀位，否则将 A[j] 放⼊到数组 tmp，j 后移⼀位

• 模板：

void merge_sort(int q[], int l, int r)
void merge_sort(int q[], int l, int r)
{
    // 终止条件
    if (l >= r) return;  
    
    // 分成子问题
    int mid = l + r >> 1;
    
    // 递归处理子问题
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    // 合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while (i <= mid && j <= r) { // 将两个空间内的数比较过后归并一个空间
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while (i <= mid) tmp[k++] = q[i++];  // 处理剩余未处理完的一个空间
    while (j <= r) tmp[k++] = q[j++];
    
    for (int k = 0, i = l; i <= r; ++i, ++k) q[i] = tmp[k];  // 复制每个tmp区间到对应的q[]中，范围为[l, r]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 注意点：

1.合并时的范围是[l，r]；