超全经典排序大汇总

算法思想

首先, 遍历原始序列确定最大值 $maxval$ 和最小值 $minval$，并确定桶的个数 $n$; 然后，将待排序集合中处于同一个值域的元素存入同一个桶中,在桶内使用各种现有的算法进行排序; 最后按照从小到大的顺序依次收集桶中的每一个元素, 即为最终结果。

inference
inference

时间复杂度

1. 最好 — $O(n + k)$
2. 最坏 — $O(n^2)$
3. 平均 — $O(n + k)$

注： $其中 k = nlog(n / m)$

演示动画

空间复杂度

$O(n + k)$

注： $其中 k = nlog(n / m)$

稳定性

稳定

算法特点

1. 桶排序是一种用空间换取时间的排序
2. 桶排序并非像常规排序那样没有限制，桶排序有相当的限制。因为桶的个数和大小都是我们人为设置的。而每个桶又要避免空桶的情况。所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀，又要要求桶的设计兼顾效率和空间。
3. 数要相对均匀分布，桶的个数也要合理设计。在设计桶排序时，需要知道输入数据的上界和下界，根据数据的分布情况考虑是否用桶排序，当然如果能用好桶排序，效率还是很高的！

算法适用性

顺序表

核心代码

//桶排序 
void BucketSort(int a[], int n){
    int minval = a[0], maxval = a[0];
    for(int i = 0; i < n; i ++){//寻找原序列数组元素的最大值和最小值 
        minval = min(minval, a[i]);
        maxval = max(maxval, a[i]);
    }

    int bnum = 10;//桶中元素个数 
    int m = (maxval - minval) / bnum + 1;//桶的个数 
    vector< vector<int> > bucket(m);

    //收集,将元素入相应的桶中. 减偏移量是为了将元素映射到更小的区间内,省内存 
    for(int i = 0; i < n; i ++) bucket[(a[i] - minval) / bnum].push_back(a[i]);

    //将桶内元素排序 
    for(int i = 0; i < m; i ++) sort(bucket.begin(), bucket.end());

    //收集, 将各个桶中的元素收集到一起 
    for(int i = 0, k = 0; i < m; i ++){
        for(int j = 0; j < bucket[i].size(); j ++){
            data[k ++] = bucket[i][j];
        }
    }
}

完整代码

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;
const int N = 200;

int data[N], num, idx; 

//桶排序 
void BucketSort(int a[], int n){
    int minval = a[0], maxval = a[0];
    for(int i = 0; i < n; i ++){//寻找原序列数组元素的最大值和最小值 
        minval = min(minval, a[i]);
        maxval = max(maxval, a[i]);
    }

    int bnum = 10;//桶中元素个数 
    int m = (maxval - minval) / bnum + 1;//桶的个数 
    vector< vector<int> > bucket(m);

    //收集,将元素入相应的桶中. 减偏移量是为了将元素映射到更小的区间内,省内存 
    for(int i = 0; i < n; i ++) bucket[(a[i] - minval) / bnum].push_back(a[i]);

    //将桶内元素排序 
    for(int i = 0; i < m; i ++) sort(bucket.begin(), bucket.end());

    //收集, 将各个桶中的元素收集到一起 
    for(int i = 0, k = 0; i < m; i ++){
        for(int j = 0; j < bucket[i].size(); j ++){
            data[k ++] = bucket[i][j];
        }
    }
}

int main(){
    //打开文件 
    ifstream infile;
    infile.open("D:\\学习\\数据结构\\第8章排序\\in.txt", ios::in);

    //写文件 
    ofstream outfile;
    outfile.open("D:\\学习\\数据结构\\第8章排序\\out.txt", ios::out);

    if(!infile.is_open()){//判断文件打开是否成功 
        cout << "file open failure!" << endl;
    }

    infile >> num;//读取元素个数 
    while(num --){//将文件中的元素复制到data[1...n] 数组中
        infile >> data[idx ++];
    }

    cout << "排序前元素序列：" << endl;
    for(int i = 0; i < idx; i ++) cout << data[i] << ' '; cout << endl;

    //cout << "使用sort函数排序后序列: " << endl;
    //sort(data, data + idx); 
    //for(int i = 0; i < idx; i ++) cout << data[i] << ' '; cout << endl;

    BucketSort(data, idx);
    cout << "使用桶排序后序列为：" << endl;
    for(int i = 0; i < idx; i ++) cout << data[i] << ' '; cout << endl;

    num = idx, idx = 0, outfile << num << endl;//写入数据数num以及在行末写入\n 
    while(num --){
        outfile << data[++ idx] << ' ';//将排序后的数据写到文件中 
    }
    outfile << endl;//向文件末尾写入\n结束符 

    //关闭文件 
    infile.close();
    outfile.close();
    return 0;
}

输入数据(in.txt)

10
13 69 86 99 59 23 64 32 86 72

输出数据(out.txt)

10
13 23 32 59 64 69 72 86 86 99