排序进阶

• 统计数字 - 蓝桥云课 (lanqiao.cn)
• 错误票据 - 蓝桥云课 (lanqiao.cn)
• 奖学金 - 蓝桥云课 (lanqiao.cn)

排序

基于比较的低效算法：

• 选择排序、插入排序、冒泡排序。时间复杂度0(n²)。

基于比较的高效算法：

• 归并排序、快速排序、堆排序。时间复杂度0(n*logn)。

基于数值划分的高效算法：

• 计数排序、基数排序、桶排序。时间复杂度0(n)。

C++的sort()函数

复杂度：O(nlogn)

sort()自带4种排序：less、greater、less_equal、greater_equal。缺省情况下，程序是按从小到大的顺序排序的，less可以不写。

示例代码：

#include<bits/stdc++.h>
using namespace std;
bool my_less(int i, int j)     {return (i < j);}  //自定义小于
bool my_greater(int i, int j)  {return (i > j);}  //自定义大于
int main (){
    int a[]={3,7,2,5,6,8,5,4};
    sort(a,a+4);                          //对前4个排序，结果：2 3 5 7 6 8 5 4
    for(int i=0;i<8;i++) cout<<a[i]<<" ";cout<<"\n";   //下面可以复制这一行打印
    sort(a,a+8,less<int>());              //结果：2 3 4 5 5 6 7 8
    sort(a,a+8,my_less); 	       //自定义排序，结果：2 3 4 5 5 6 7 8
    sort(a,a+8,greater<int>());           //从大到小排序，结果：8 7 6 5 5 4 3 2
    sort(a,a+8,my_greater);               //结果：8 7 6 5 5 4 3 2

    vector<int> c = {1,2,3,4,5,6,7,8};
    sort(c.begin(),c.end(),my_greater);   //结果：8 7 6 5 4 3 2 1
    for(int i=0; i<c.size(); i++)  cout<<c[i]<<" ";cout<<"\n";

    string s="hello world";
    sort(s.begin(),s.end());
    cout<<s;                              //输出 dehllloorw      注意第一个是空格
    return 0;
}

计数排序

例：{9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9}。

先找出最大值 10 和最小值为 0，对应计数范围是0 ~ 10。

然后每一个整数按照其值对号入座。

• 第一个整数是9：a[9]加1

• 第二个整数是3：a[3]加1

• 第三个整数是5：a[5]加1

• 每个数字对号入座，a[i]的值等于数字i出现的次数

• 输出：遍历数组a[]，a[i]的值是几，就输出i几次

• 计算复杂度：O(n+k) n是数字的个数，k是数字的范围

• 空间复杂度：O(k)

• 当n和k接近时，计数排序很好

局限性：

• 数列最大最小值差距过大时，不适用于计数排序。例如20个随机整数，范围在 0 到 1 亿之间，如果使用计数排序的话，就需要创建长度为 1 亿的数组，严重浪费了空间，而且时间复杂度也随之升高。

• 当数列元素不是整数时，并不适用于计数排序。

快速排序

• 把序列分成左右两部分，使得左边所有的数都比右边的数小；

• 递归这个过程，直到不能再分为止。

• 如何把序列分成左右两部分？最简单的办法是设定两个临时空间X、Y和一个基准数t；检查序列中所有的元素，比t小的放在X中，比t大的放在Y中。

• 不过，其实不用这么麻烦，直接在原序列上操作就行了，不需要使用临时空间X、Y。

复杂度：

• 每一次划分，都把序列分成了左右两部分，在这个过程中，需要比较所有的元素，有O(n)次。

• 如果每次划分是对称的，左右两部分的长度差不多，那么一共需要划分O(logn)次。

• 总复杂度O(nlogn)。

优点：

• 一般情况下快速排序效率很高，比稳定的归并排序更好。

• 可以观察到，快速排序的代码比归并排序的代码简洁，代码中的比较、交换、拷贝操作很少。

• 快速排序几乎是目前所有排序法中速度最快的方法。

缺点：

• 如果划分不是对称的，左部分和右部分的数量差别很大。在极端情况下，例如左部分只有1个数，剩下的全部都在右部分，那么最多可能划分n次，总复杂度是O(n²)。

• 所以，快速排序是不稳定的。

归并排序

归并排序是由递归实现的，主要是分而治之的思想，也就是通过将问题分解成多个容易求解的局部性小问题来解开原本的问题的技巧。

归并排序在合并两个已排序数组时，如果遇到了相同的元素，只要保证前半部分数组优先于后半部分数组， 相同元素的顺序就不会颠倒。所以归并排序属于稳定的排序算法。

每次分别排左半边和右半边，不断递归调用自己，直到只有一个元素递归结束，开始回溯，调用 merge 函数，合并两个有序序列，再合并的时候每次给末尾追上一个最大 int 这样就不怕最后一位的数字不会被排序。

示例：