算法学习专栏——排序算法（一）

前言

接下来我们将要讲解的是排序算法，但是我们一般情况下是很少会直接用到这些算法的，因为我们C++有内置的排序函数sort()，这个内置函数使用的排序算法实际上是快速排序+优化决策，比我们下面会介绍的快速排序的速度还要快上4倍左右。

但是我们任何需要了解如何使用这个算法，因为这是你入门的必经之路！本人目前所见过的排序算法已有10种多，下面我将为大家讲解以下5种最值得讲解的排序算法，分别是：桶排序、计数排序、快速排序、归并排序和堆排序。

前两种排序方式较为简单，后面三种排序算法可能会比较吃力，因此分两天介绍这5种算法，今天介绍的是前三种排序方式，明天介绍后两种。

一、桶排序介绍

原理

桶排序使用的主要就是分治思想，这个思想对我们之后解题可以拓展思路。

这里所谓的分治思想就可以举个例子：现在有30个小球，每个小球上有一个数（这个数在1和990之间），需要你从小到大排序，对这个数一起排序，你应该会非常头疼。这时候你就可以选择找来30个桶（桶的数量一般要远小于球的个数，这里我只是为了大家好观察才取了30个桶），我们就可以规定从第一个桶开始，每个桶放的数每30 个一隔，比如第1个桶放1~30这些数，第2个桶放30 ~ 60这些数，以此类推……

然后我们取到一个数来判断这个数应该在哪个桶里，接着再在这个桶里对这个数进行排序，这是不是就轻松了很多。最后所有的数放好之后，就只需要按照从第1个桶到第30个桶的顺序依次将小球拿出来就可以将这30个小球排序完毕了，大家可以看看下面的动画进行理解一下。

实现代码

答案（请自己先思考一下再参考）

        
#include< iostream>
#include< vector>
#include< algorithm>     //sort
#include< ctime>
using namespace std;
const int N = 10;       //桶的个数 数据范围设为0 - 100(左闭右开)
//桶排序 设置几个桶，放入元素并对桶内排序(采用sort)
void BucketSort(vector < int> &a){
    int n = a.size();
    vector> bucket(N);
    for(int i = 0; i < n; i++)
    bucket[a[i] / 10].push_back(a[i]);
    //将每个元素放入对应桶中	
    int k = 0;
    for(int i = 0; i < N; i++){
        //对每个桶进行排序
        sort(bucket[i].begin(), bucket[i].end());
        int size = bucket[i].size();
        for(int j = 0; j < size; j++)
            a[k++] = bucket[i].at(j);      //放入原数组    	
    }
    vector>().swap(bucket);    //释放空间
}
void show(vector< int> &v){
    for(auto &x : v)
    cout< a;
    srand((int)time(0)); // 随机数种子，不了解也可以，重点看上面的BucketSort()函数
    int n = 50;
    while(n--)
    a.push_back(rand() % 100);   //数据范围[0, 99]
    show(a);
    BucketSort(a);
    cout<

二、计数排序

原理

2月12日晚上讲解到过的一种思想。先给出一个数组cnt[N]。现在输入一些数，假设输入3，则cnt[3]++；输入5，则cnt[5]++。这个cnt就是用来统计各个数出现次数的，cnt[x]表示的就是x出现的次数，看下图也可以很清楚知道。

代码

答案（请自己先思考一下再参考）

        
#include < iostream>
using namespace std;
const int N = 1e4 + 10;
int cnt[N];
int main()
{
    int n;
    cin >> n; // 輸入需要排序的数的个数
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    for (int i = 0; i <= 10000; i++) { // 假设这些数的范围为0~10000
        while (cnt[i]--) {
            cout << i << " ";
        }
    }
    return 0;
}

三、快速排序（简单+）

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9^ 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

1 2	`5 3 1 2 4 5`

输出样例：

1	`1 2 3 4 5`

思路

直播（录屏）

Comparison Sorting Visualization （拙劣版本快速排序）

代码

答案（请自己先思考一下再参考）

        
#include < iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;
void quick_sort(int l,int r) {
    if (l >= r) return;
    int ll = l - 1,rr = r + 1,mid = l + r >> 1,x = a[mid];
    while (ll < rr) {
        do ll++; while(a[ll] < x);
        do rr--; while(a[rr] > x);
        if (ll < rr) swap(a[ll], a[rr]);
    }
    quick_sort(l, rr);
    quick_sort(rr + 1, r);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    quick_sort(0, n - 1);    
    for (int i = 0; i < n;i ++) {
        cout << a[i] << " ";
    }   
    return 0;
}

算法学习专栏——排序算法（二）上一篇

算法学习专栏——Tire算法下一篇