henrytb 的博客

henrytb 的博客

ZROI 9.9 排序

posted on 2018-09-09 09:09:28 | under ZROI |

$$ O(n^2)\text{ 排序算法 }$$


$$\text{ 选择排序 }$$

每次找最大(或最小)的一个数,放到对应位置。


$$\text{ 插入排序 }$$

for一遍,每次往前查,找到相应位置。


$$\text{ 冒泡排序 }$$

n轮,每次比较相邻元素。

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(a[i]>=a[j])swap(a[i],a[j]);

思考:逆序对


$$ O(nlogn)\text{ 排序算法 }$$


$$\text{ 快速排序 }$$

  • 每次随机选择一个数作为分界点
  • 大的放右边小的放左边
  • 递归对两边分治
void work(int L,int R){
    if (L>=R) return;
    int i=L,j=R,tmp=A[(L+R)/2];
    while (i<=j){
        while (i<=j&&A[i]<tmp) i++;
        while (i<=j&&A[j]>tmp) j--;
        if (i<=j){
            swap(A[i],A[j]);
            i++,j--;
        }
    }
    if (i<R) work(i,R);
    if (L<j) work(L,j);
}

如知道随机种子或每次选中间数,如何卡至 $O(n^2)$ ?
使中间数为最小值。

STL大法吼!

sort(a,a+n); //a[0..n-1]
sort(a.begin(),a.end()); //vector
sort(a.rbegin(),a.rend()); //sort+reverse (vector)
//------------------------------------------------
bool cmp(aaa a,aaa b){
    return a.aa<b.aa;
}
sort(a,a+n,cmp);
//------------------------------------------------
bool operator < (aaa a,aaa b){
    return a.aa<b.aa;
}
sort(a,a+n);

STL比较函数当两个数相等的时候一定要返回0!!!

Reverse Sort:

  • 给你一个序列,每次操作能翻转一个区间,代价为这个区间的长度
  • 在 $O(nlogn)$ 的总代价内将整个序列排序

$$\text{ 归并排序 }$$

  • 从中间断开为左右区间
  • 递归对两边分治
  • 对已经有序的两边区间进行归并
void work(int L,int R){
    if (L==R) return;
    work(L,Mid);
    work(Mid+1,R);
    int tl=L,tr=Mid+1,t=L;
    while (tl<=Mid&&tr<=R){
        if (A[tl]<A[tr]) B[t++]=A[tl++];else B[t++]=A[tr++];
    }
    while (tl<=Mid) B[t++]=A[tl++];
    while (tr<=R) B[t++]=A[tr++];
    for (int i=L;i<=R;i++) A[i]=B[i];
}

STL大法吼!

区间合并:inplace_merge

//a[0..n-1],a[n..n*2-1]合并
inplace_merge(a,a+n,a+n*2);

扩展:归并排序求逆序对


$$\text{ 不基于比较的排序算法 }$$


$$\text{ 桶排序 }$$

一个萝卜一个坑

时间复杂度 $O(n+m)$


$$\text{ 基数排序 }$$

  • 分段分别桶排,从低位到高位依次作为关键字
  • 比如设当前所有数已经按后?位排好了序,那么后?+1位的排序就是按第?+1位排,相同的就按原顺序排
  • 视段长的大小,开这么多的桶,求出比?小的数有多少个,然后快速把每个数放到该放的位置去。

[WC2017] 挑战