排序

发表于 阅读次数：

STL

1
2
3
4
5
6
7
8
9
10
bool compare(your_own_node a, your_own_node b) {
    return a.v < b.v;
}
sort(* + 1, * + len + 1, compare);
//不加compare默认从小到大

bool operator < (your_own_node a, your_own_node b) {
    return a.v < b.v;
}
//重载运算符也可以用于sort，但是不能重载int这样的系统数据结构。

排序不简单

应该有很多选手和我一样，虽然名义上学过排序，但到了考场就只会一行代码：

1
sort(a + 1, a + n + 1, cmp);

不要说快速排序了，连冒泡都不一定打得出完整的。统计逆序对也不会归并，只会用树状数组+离散化（烦得要死）甚至干脆用冒泡跑暴力。

直到下一届的新生开始学排序，我才发现：我甚至连快排都不会！

今天，就以模板题P1177来扒一扒，怎么写出又快又简洁的快速排序。

基础算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void qsort(int l, int r) {
    int mid = a[(l + r) >> 1];
    int i = l,j = r;
    do {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if(i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    } while(i <= j);
    if(l < j) qsort(l, j);
    if(i < r) qsort(i, r);
}

似乎这么打就能过了。但让我一直不解的是，用《算法导论》上的代码，死活都过不了。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Partition(int *arr, int beg, int end) {
    int sentinel = arr[end];
    int i = beg - 1;
    for(int j = beg; j <= end - 1; ++j) {
        if(arr[j] <= sentinel) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[end]);
    return i+1;
}
 
void QuickSort(int *arr, int beg, int end) {
    if(beg < end) {
        int pivot = Partition(arr, beg, end);
        QuickSort(arr, beg, pivot-1);
        QuickSort(arr, pivot+1, end);
    }
}

即使是加了随机化，仍然慢的要死，甚至递归到爆栈。
下了一个数据点，简直被吓死。看一下这数据的险恶：

这跑个屁呀!

分析一下就可以发现，《算法导论》中的算法选取的是最右端的数作为基准，所以面对完全相同的数据，即使随机化，所有的数也都落在基准的一侧，直接退化为 \(O(n^2)\) 。所以，要想快排写的快，取中间的数做基准。

归并排序 & 逆序对

逆序对是满足 \(i < j\) 且 \(a_i > a_j\) 的有序数对 。

我们可以发现，归并排序中将两个数组合并时，较靠后的数组每被取出一个数，意味着它和较靠前的数组剩下的所有数都产生了逆序对。而且容易发现，这样的统计是不重不漏的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[maxn], b[maxn];
long long sum; /*****long long is important!*****/

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    for (int i = l; i <= r; i++) b[i] = a[i];
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (j > r || (i <= mid && b[i] <= b[j])) a[k] = b[i++]; /*****<= is important*****/
        else a[k] = b[j++], sum += mid - i + 1;
    }
}