本周继续介绍排序算法。

快速排序

快速排序与归并排序的策略有些类似，基本思想也是分治法，首先从待排序列中找一个主元，根据这个主元将待排序列的所有元素划分为两部分，一部分比它小，另一部分比它大，然后对两个子部分在进行划分和排序，依次重复操作，最后再将这些合并为一个序列。基本代码如下：

void Quick_Sort(ElementType A[], int N) {
    if(N < 2) return;
    pivot = 从A[]中选一个主元;
    将S = {A[] / pivot} 分成2个独立子集;
        A1 = {a ∈ S | A <= pivot};
        A2 = {a ∈ S | A >= pivot};
    A[] = Quick_Sort(A1, N1)∪(pivot)∪Quick_Sort(A2, N2);
}

按照上述的伪码描述，快排需要解决的问题有两个：

1. 如何去选主元
2. 如何进行子集划分

很明显，按照思路，能把第一个问题解决了，第二个问题也就迎刃而解了。

选主元

那么主元应该怎么去选择呢？比较经典的方法就是取头、中、尾三个数（当然也可以五个数）的中位数（以序列{8, 12, 3}为例，它的中位数是8），选主元时，可以顺便将待选的三位数进行排序，这样当选出主元后，也可以待排序列数据的总个数减少，基本代码如下：

ElementType Median3(ElementType A[], int Left, int Right)
{
    int Center = (Left + Right)/2;
    if(A[Left] < A[Center]) Swap(&A[Left], &A[Center]);
    if(A[Left] < A[Right]) Swap(&A[Left], &A[Right]);
    if(A[Center] < A[Right]) Swap(&A[Center], &A[Right]);
    /*after finish swap, A[Left] <= A[Center] <= A[Right]*/
    /*put the pivot to A[Right-1], then only consider the sequence from
	 A[Left+1] to A[Right-2]*/
    Swap(&A[Center], &A[Right-1]);
    return A[Right-1];
}

按照上述代码，因为最后将pivot放到了Right-1位置，所以，另外两个元素的位置就可以不用在考虑了，只考虑区间$[Left+1, Right-1]$内的元素即可。

子集划分

子集划分时，需要使用两个指针，一个首，一个尾，当尾指针小于首指针（两者已交叉）时，说明子集的划分已完成。在进行这个操作时，会存在一个问题，那就是遇到相等的元素怎么办？
以最坏的情况（序列元素全部相等）为例，如果采取直接交换元素的方法，那么首、尾指针的每一次变化，都需要交换一次元素，结束后，主元pivot会被放在中间的位置，这样下一次循环的时候就会将剩下的序列在等分成两个序列，这样时间复杂度就是$O(NlogN)$了；那如果跳过相等的元素呢？在最坏的情况下，会有一端的指针停滞不前，那么每次就只有一个指针在移动，这样每次得到的子序列就$N, N-1, N-2, \dots, 1$了，那样时间复杂度依然是$O(N^2)$，所以还是采取交换元素的方法。
另外，如果数据规模较小的话，，特别是数据总数连100都不到的时候，对于依然使用递归的快速排序而言，就不是那么划算了，所以需要做个判断，在数据规模较小的时候，采取其他的排序方式。

算法实现

选好主元，明确子集的划分方法，就可以来构造算法了，基本代码如下：

void QuickSort(ElementType A[], int Left, int Right)
{
    if(Cutoff <= Right-Left){
        Pivot = Median3(A, Left, Right);
        i = Left;
        j = Right - 1;
        for(; ; )
        {
            while(A[++i] < pivot);
            while(A[--j] > pivot);
            if(i < j) Swap(&A[i], &A[j]);
            else break;
        }
        Swap(&A[i], &A[Right-1]);
        QuickSort(A, Left, i-1);
        QuickSort(A, i+1, Right);
    }else Insertion_Sort(A+Left, Right-Left+1);
}

上述代码的思路比较直观，先选好主元，在进行子集划分，然后将主元放到靠近中间的位置，此时主元的位置与最终结果序列的位置是一致的，这点与冒泡排序一样，每次都会有一个元素被排到最终位置。当待排元素小于阈值Cutoff时，直接使用插入排序解决剩下的元素序列。

表排序

表排序适用于待排元素不是简单的整数，而是复杂、庞大的元素的时候，因为这些复杂、庞大的元素的交换和移动会十分费时。也就是说，表排序在排序过程中不需要移动元素，只需要移动指针即可，这种不移动元素，只移动指针的排序方法称为间接排序。
定义一个指针数组作为“表”（table），表排序算法的操作对象就是这个“表”了。

物理排序

假若仍然需要移动实际的元素来完成排序，那么可以根据下面这个结论在线性的时间复杂度内完成这个操作。

定理：N个数字的排列由若干个独立的环组成。

这里的“环”，其实是一个比较抽象的概念，指的是经过表排序后等到的table内，有些元素的顺序会形成一个序列，而这个序列就称作“环”。下面来看个例子，表排序前：

A	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
key	f	d	c	a	g	b	h	e
table	0	1	2	3	4	5	6	7

表排序后：

A	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
key	f	d	c	a	g	b	h	e
table	3	5	2	1	7	0	4	6

上表中，由{3, 5, 1, 0}这个下标序列可得对应的有序序列为{a, b, d, f}，这个序列是有序的，其对应关系如下表：

A	[0]	[1]	[3]	[5]
table	3	5	1	0

由上表中构成的关系，就是“环”，可以根据“环”得到有序的序列。
紧接着，根据这些有序的序列，借助一个临时空间，遍历一次这个有序序列，就可以完成物理序列的排序。很明显可以得到，当table[i] == i时，环就结束了。

时间复杂度分析

当初始序列为有序时，是最好的情况；当有$\lfloor N/2 \rfloor$个环时，每个环包含2个元素，交换两个元素需要三步操作，就需要$\lfloor 3N/2 \rfloor$次元素移动，而表排序针对的就是元素移动时间较长的存储结构，所以时间复杂度为$T = O(m\ N)$，$m$为每个元素的复制时间。

基数排序

基数排序与其他排序算法有一个很大的差别，那就是不仅只是比大小了，因为单纯靠比较大小的排序算法的时间复杂度最低只能是$T(NlogN)$这个级别，所以得在添点“料”来继续提升速度，下面先来看看桶排序。

桶排序

对于桶排序而言，假设待排序列有$N$个元素，先申请$N$个桶（有序，桶内保存指针），然后将每一个符合条件的值，插到这个有序的桶排列中，这样就可以了，大致代码如下：

void Bucket_Sort(ElementType A[], int N) {
    count[]初始化;
    while(读入一个数据) {
        将该数据插入count[桶内保存的指针++];
    }
    for(i=0; i<M; i++) {
        if(count[i]){
            输出count[i]整个链表;
        }
    }
}

按照上述的伪码，有$N$个数据需要读入，$M$个数据需要输出，所以时间复杂度为$T(N, M) = O(M + N)$。但是当$M >> N$的情况下，使用桶排序就不是那么划算了，这就需要使用基数排序了。

桶排序基本思想

了解了桶排序之后，基数排序就好理解了，基数排序建桶规则是按照给定数据的进制数建桶，例如{78, 123, 44, 678}，这个序列的数都是十进制的，所以基数（桶的大小）为 10。

基数排序算法的主体思想采用的是次位优先（Least Significant Digit）的思想（也可以使用主位优先(Most Significant Digit)），简单来讲，第一次排序以个位数大小为基准来排序，第二次排序以十位数大小为基准来排序，但需要将第一次排序中的高位数拿出来，重复至最高位排完后结束。每躺排序过程中，需要访问$N$个结点，也需要访问$B$个桶，所以时间复杂度为$T=O(P(N+B))$。

多关键字排序

扑克牌的花色就是一种“多关键字排序”，不同花色同花顺也有大小之分。

以为扑克牌排序为例，扑克牌有两种属性，分别是花色和大小，一副整齐的扑克牌，花色和大小必定都是整齐的，根据基数排序的思想，我们可以先按照大小来做基数排序，这需要13个桶来完成，排好序后，各个桶中的牌的大小都是相等的，此时我们在以花色为基数建桶，依次取出花色按顺序取出花色相同的牌放到不同花色的桶内即可，已经不需要根据大小排序了。

排序算法的比较

排序方法	平均时间复杂度	最坏情况时间复杂度	额外空间复杂度	稳定性
简单选择排序	$O(N^2)$	$O(N^2)$	$O(1)$	不稳定
冒泡排序	$O(N^2)$	$O(N^2)$	$O(1)$	稳定
直接插入排序	$O(N^2)$	$O(N^2)$	$O(1)$	稳定
希尔排序	$O(N^d)$	$O(N^2)$	$O(1)$	不稳定
堆排序	$O(NlogN)$	$O(NlogN)$	$O(1)$	不稳定
快速排序	$O(NlogN)$	$O(N^2)$	$O(logN)$	不稳定
归并排序	$O(NlogN)$	$O(NlogN)$	$O(N)$	稳定
基数排序	$O(P(N+B))$	$O(P(N+B))$	$O(N+B)$	稳定

尽管上表中给出了各排序算法的具体的时间复杂度，但是实际应用时还是需要根据实际情况来选择合适的排序算法。另外，从表中看到堆排序的性能比较好，但是实际效果不太理想。除了这些基础排序算法外，还有很多其他的排序算法，那些也值得进一步学习。

Homework

10-4 统计工龄

这个题目很简单，借助一下姥姥课上讲的桶排序的思想即可，C++ 语法的代码如下：

#include <iostream>

int main() {
    int n;
    std::cin >> n;
    int staff[55] = { 0 }, tmp;
    for (int i = 0; i < n; i++) {
        std::cin >> tmp;
        staff[tmp]++;
    }
    for (int i = 0; i < 52; i++) {
        if (staff[i]) std::cout << i << ':' << staff[i] << std::endl;
    }
    return 0;
}

/*
samples:
in:
8
10 2 0 5 7 2 5 2
out:
0:1
2:3
5:2
7:1
10:1

in:
10
10 2 0 0 0 5 7 2 5 2
out:
0:3
2:3
5:2
7:1
10:1
*/

10-5 PAT Judge

这道题目的出题背景应该就是 PAT 的排名系统了，但其实是甲级题库的一道排序题，需要按照题目的要求来进行排序，直接使用 C++ 的库函数会方便许多。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 10000 + 5;
struct user{
    int id, scores[6], sum, perfect;
    bool flag;
} us[maxn];
int n, k, m, p[6] = {0};
bool cmp(user a, user b) {
    if(a.sum != b.sum) return a.sum > b.sum;
    else if(a.perfect != b.perfect) return a.perfect > b.perfect;
    else return a.id < b.id;
}
void init() {
    for(int i = 1; i <= n; i++) {
        us[i].id = i;
        us[i].sum = us[i].perfect = 0;
        us[i].flag = false;
        memset(us[i].scores, -1, sizeof(us[i].scores));
    }
}
int main() {
    scanf("%d %d %d", &n, &k, &m);
    init();
    for(int i = 1; i <= k; i++) {
        scanf("%d", p + i);
    }
    int id, proid, scoob;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &id, &proid, &scoob);
        if(scoob != -1) us[id].flag = true;
        if(scoob == -1 && us[id].scores[proid] == -1) us[id].scores[proid] = 0;
        if(scoob == p[proid] && us[id].scores[proid] < p[proid]) us[id].perfect++;
        if(scoob > us[id].scores[proid]) us[id].scores[proid] = scoob;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            if(us[i].scores[j] > 0) us[i].sum += us[i].scores[j];
        }
    }
    sort(us + 1, us + n + 1, cmp);
    int rank = 1;
    for(int i = 1; i <= n && us[i].flag; i++) {
        if(i > 1 && us[i].sum != us[i - 1].sum) rank = i;
        printf("%d %05d %d", rank, us[i].id, us[i].sum);
        for(int j = 1; j <= k; j++) {
            if(us[i].scores[j] == -1) printf(" -");
            else printf(" %d", us[i].scores[j]);
        }
        putchar('\n');
    }
    return 0;
} 

/*
samples:
in:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0
out:
1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

in:
3 4 9
20 25 25 30
00001 3 30
00002 3 30
00003 3 30
00001 3 30
00002 3 20
00003 3 20
00001 3 30
00002 3 10
00003 3 30
out:
1 00001 30 - - 30 -
1 00002 30 - - 30 -
1 00003 30 - - 30 -

in:
2 2 6
20 20
00001 1 -1
00002 1 -1
00001 1 -1
00002 1 -1
00001 1 -1
00002 1 0
out:
(blank)
*/

10-6 Sort with Swap(0, i)

这个题不太好想，但是与表排序非常类似。

#include <iostream>
using namespace std;
const int maxn = 100000 + 5;
int pos[maxn], n, ans = 0;
int main() {
    cin >> n;
    int remains = n - 1, tmp;
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        pos[tmp] = i;
        if(tmp == i && tmp != 0) remains--;
    }
    int k = 1;
    while(remains > 0) {
        if(pos[0] == 0) {
            while(k < n) {
                if(pos[k] != k) {
                    swap(pos[0], pos[k]);
                    ans++;
                    break;
                }
                k++;
            }
        }
        while(pos[0] != 0) {
            swap(pos[0], pos[pos[0]]);
            ans++;
            remains--;
        }
    }
    cout << ans;
    return 0;
}

/*
samples:
in:
10
3 5 7 2 6 4 9 0 8 1
out£º
9

in:
5
4 0 2 1 3
out:
3

in:
3
0 2 1
out:
2

in:
5
4 3 2 1 0
out:
4

*/