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

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

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

Note:

简单排序

插入排序:

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

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

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

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

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++;
}

函数的接口比较

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

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

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

复用性

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

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

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

冒泡排序

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

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以后的元素已经有序,所以我们可以优化(虽然依然是 $$ O(n^2) $$ 但是优化了一半的常数)。

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]前就已经有序了,所以无需排序。

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)的实用算法

归并排序是基于分治思想的排序,做到了比较算法的极限,达到了$$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=1pb=1

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

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

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个元素了,站队完成就是排序好的序列。

这样就完成排序了!

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 定理

主定理,可以用于算递归函数复杂度:

$$ T(n) = aT(n/b) +O(n^d) $$

有:

$$ T(n)=\left\{ \begin{aligned} O(n^d) && d>log_{b}a\newline O(n^dlogn) && d=log_{b}a\newline O(n^{log_ba}) && d<log_{b}a\newline \end{aligned} \right. $$

This post was written on July 23, 2022.