本文实际上是我23日补写的。

排序(sort)是有个非常有意思的算法，今天我们学习了：插入排序、冒泡排序，选择排序。以及可以在做题中使用的：归并排序和快速排序。所有基于比较的排序最低时间复杂度是O(nlogn)*.

有的时候排序并不直接解决问题，但可以起到加速作用；有些算法依赖于 排序。

Note：

简单排序

插入排序：

有的时候排序并不直接解决问题，但可以起到加速作用；有些算法依赖于 排序。

插入排序是在一个已经有序的序列中插入数据，插入后序列依然是一个有序的序列。

即维护一个有序的序列，不断插入元素。

所以我们只要写一个insert()函数，插入序列即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
void insert(int x){
	int pos=0;
	for(;pos<tot;pos++){
		if(a[pos]>x){
			for(int k=tot;k>=pos,k--){
				a[k+1]=r[k];
			}
			break;
		}
	}
	a[pos]=x;
	tot++;
}

函数的接口比较

1
void insert()
1
void insert(int x)
1
void insert(int a[],int x)

很明显，最后一种比前两种要好。

因为有DRY(Do not repeat yourself)原则，所以最后一种要更好，可以应对不同的需求。当然，如果你只需要排序一个数组，且第二种更方便，那么第二种也是可行的。

复用性

如果需要第三种接口支持从大到小排序，甚至按自定义的顺序？ 如果不仅要排序 int，还要排 float、字符串、甚至自定义的结构体？
如果不知道数组长度，但数组有一个结束标识符？

越抽象越容易复用，越具体越不容易复用。
良好的代码风格会使你付出 1.2 倍的编码时间，但会减少一半的调试时间。
抽象要有个度，如果泛化的收益抵不上代码复杂程度增加带来的坏处，果断停手

总结：在OI中无需工业级别的服用，但是也需要注意复用性。

冒泡排序

将每个元素比较n次，如果遇到比它大或小的元素就交换，在每个元素都比较一遍过后，整个序列就都是有序的。整个过程如冒泡一样，故人们称它为冒泡排序。只是时间复杂度有亿点大：这是一个很大的时间复杂度，但是他的思想是值得我们学习的。

1
2
3
4
5
6
void bubble(int a[],int n){
	for(int i=0;i<0;i++)
		for(int j=0;j<n;j++)
			if(a[j]>a[i])
				swap(a[j],a[i]);
}

第一次冒泡会把最大的放到最后，第二次是次大，所以在执行第i次排序时，n-i以后的元素已经有序，所以我们可以优化（虽然依然是但是优化了一半的常数)。

1
2
3
4
5
6
void bubble(int a[],int n){
	for(int i=0;i<0;i++)
		for(int j=0;j<n-i-1;j++)
			if(a[j]>a[i])
				swap(a[j],a[i]);
}

选择排序

选择排序的思路是找到最小值，然后与a[1]交换，找到次小值，与a[2]交换。因为是选择元素交换，故称之为选择排序。他的优化与冒泡类似，在排序i次后a[i]前就已经有序了，所以无需排序。

1
2
3
4
5
6
7
8
9
void select(int a[],int n){
	for(int i=1;i<=n;i++){
		int cur=i;
		for(int j=i;j<=n;i++)
			if(a[j]<a[i])
				cur=i;
		swap(a[i],a[cur]);
	}
}

O(nlogn)的实用算法

归并排序是基于分治思想的排序，做到了比较算法的极限，达到了的时间复杂度，且十分稳定，非常的优秀。

将a[l,r]排序：

  1. 将a[l,r]拆成a[l,mid]和a[mid+1,r]分别递归排序，这样递归到序列只剩一个的时候就是一个有序的序列。
  2. 调用sort(l,mid)和sort(mid+1,r)递归排序
  3. 将两个有序数组，合并成一个大的有序数组，覆盖 a[l,r]

难点就在于合并。

合并

现在有2个序列a[1,2,3]和b[4,5,6]，他们都是有序的，建第三个序列tmp。

现在定义pa,pb两个指针，初始值为pa=1，pb=1。

如果a[pa]>a[pb]那么将a[pa]放入tmp[pos++]然后pa++反之将a[pb]放入tmp[pos++]然后pb++。

这样就完成了2个有序序列的合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Sort(int l, int r) {
    if(l == r - 1) return;      // 现在区间里面只有一个元素，直接返回即可
    int mid = (l + r) / 2;
    Sort(l, mid);  // 递归左边
    Sort(mid, r);  // 递归右边
	// 递归后[l,mid],[mid,r]已经有序，合并即可
    int p=l, q=mid, cur=l;
    // 左边现在可以使用的是 a[p, mid)
    // 右边现在可以使用的是 a[q, r)
    // 答案数组目前要填写 tmp[cur]
    while(p < mid && q < r) {
        if(a[p] < a[q])
            tmp[cur++] = a[p++];
        else
            tmp[cur++] = a[q++];
    }
    while(p < mid)               // 若左边还没有取干净
        tmp[cur++] = a[p++];
    while(q < r)                 // 若右边还没有取干净
        tmp[cur++] = a[q++];
	//合并完成，直接填入tmp
    for(int i=l; i<r; i++)
        a[i] = tmp[i];
}

因为每次都是(l+r)/2分开，所以需要递归logn层，每次n的代价，所以时间复杂度为O(nlogn)。

这样的排序是非常稳定的！

快速排序

叫做快速排序自然有过人之处，他的思想非常的有意思：

随便选一个人做哨兵，比它小的人站在左边，大的人站在右边，然后递归排序左边和右边，这样就是有序的了。

例子

我们需要排序序列：[3,2,5,4,8,7,6,1]

  1. 随便选了个人，身高为 4
  2. 站队，序列变成 [3,2,1] 4 [5,8,7,6]
  3. 分别排序，序列变成 [1,2,3] 4 [5,6,7,8]

递归到底层就只有3个元素了，站队完成就是排序好的序列。

这样就完成排序了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void quickSort(int l, int r) {
    if(l >= r - 1) return;      // 现在区间是空集，或只有一个元素

    int flag = a[l + rand() % (r - l)];     // 随机选个哨兵
    // 假设永远选 a[l] 做哨兵
    // 出题人：a=[10,9,8,7,6,5,4,3,2,1]
    // 第一次调用：哨兵10 [9 8 7 6 5 4 3 2 1] [10]
    // 第二次调用：哨兵9  [8 7 6 5 4 3 2] [9]
    // ...
    // 总共复杂度是 O(n^2)

    int p = l, q = r;
    // tmp[l, p) 存放比 flag 小的人
    // tmp[q, r) 存放比 flag 大的人

    for(int i=l; i<r; i++) {
        if(a[i] < flag)
            tmp[p++] = a[i];    // 等价于 tmp[p]=a[i], p++
        else if(a[i] > flag)
            tmp[--q] = a[i];    // 等价于 q--, tmp[q]=a[i]
    }

    for(int i=p; i<q; i++)      // [p, q) 应当填充恰等于哨兵的人
        tmp[i] = flag;

    // 现在局面：tmp[l, p) < flag; tmp[p, q) == flag; tmp[q, r) > flag

    for(int i=l; i<r; i++)
        a[i] = tmp[i];          // 回填进a
    
    // 站队已经完成，递归排序左边、右边
    quickSort(l, p);
    quickSort(q, r);
}

Leaned:

简单排序：复杂度 O(n2)
归并排序：复杂度 O(nlogn) (有保障)
快速排序：平均复杂度 O(nlogn)

Master 定理

主定理，可以用于算递归函数复杂度：

有:

This post was written on July 23, 2022.