超全经典排序大汇总

算法思想

将整个关键字拆分为d位(或“组”), 按照各个关键字权重递增的次序(如：个、十、百), 做 $d$ 趟“分配”和“收集”, 若当前处理的关键字位可能取得 $r$ 个值,则需要建立 $r$ 个队列,顺序扫描各个元素, 根据当前处理的关键字位, 将元素插入到相应的队列, 把各个队列中的结点,依次出队并连接。

inference
inference

时间复杂度

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

注：
1. 以 $r$ 为 基数, 例如：十进制 $r = 10$
2. $n$ 表示有 $n$ 个记录
3. $d$ 表示每个记录含的关键字个数
4. 时间复杂度与序列初始状态无关

演示动画

空间复杂度

$O(r)$

稳定性

稳定

算法特点

1. 稳定排序
2. 可用于链式结构和顺序结构
3. 时间复杂度可以突破关键字比较方法的下界, $O(nlogn)$ 达到 $O(n)$
4. 技术排序使用条件严格,必须知道各级关键字主次关系和各级关键字的取值

算法适用性

1. 顺序表
2. 链表

朴素版(不可以对负数排序)

核心代码

//基数排序 
void RadixSort(int a[], int n){
    const int RADIX = 10;//DADIX表示为十进制数 
    int maxval = a[0], minval = a[0], base[10];//base数组存的是十进制数的位权 
    vector< vector<int> > bucket(RADIX);//相当于定义10个桶 

    base[0] = 1;//个位的权值为 1 
    for(int i = 1; i < 10; i ++) base[i] = base[i - 1] * 10;//初始化权值 
    for(int i = 0; i < n; i ++){
        maxval = max(maxval, a[i]);//求出所有元素的最大值 
    }

    int dnum = ceil(log10(maxval + 1));//求出最大的位数,比如38为2位 

    for(int d = 0; d < dnum;  d ++){//枚举每一位,共dnum趟 
        for(int i = 0; i < n; i ++){//枚举每一个数 
            int t = (a[i] / base[d]) % RADIX;//取出该位数值,即对应的桶号 
            bucket[t].push_back(a[i]);//将当前数值放入桶中(对应位) 
        }

        for(int i = 0, j = 0, k = 0; i < n; ){//i为当前元素下标,j为桶的编号
            if(k < bucket[j].size()){//k为桶中的第k号元素 
                a[i ++] = bucket[j][k ++];//依次将桶中元素存入数组(已按当前位有序) 
            }
            else j ++, k = 0;//枚举下一个桶,从该桶中第0号元素开始 
        }
        for(auto &v : bucket) v.clear();//将桶中元素清零, 开始下一趟排序 
    }
}

完整代码

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

using namespace std;
const int N = 10000;

int data[N], num, idx; 

//基数排序 
void RadixSort(int a[], int n){
    const int RADIX = 10;//DADIX表示为十进制数 
    int maxval = a[0], minval = a[0], base[10];//base数组存的是十进制数的位权 
    vector< vector<int> > bucket(RADIX);//相当于定义10个桶 

    base[0] = 1;//个位的权值为 1 
    for(int i = 1; i < 10; i ++) base[i] = base[i - 1] * 10;//初始化权值 
    for(int i = 0; i < n; i ++){
        maxval = max(maxval, a[i]);//求出所有元素的最大值 
    }

    int dnum = ceil(log10(maxval + 1));//求出最大的位数,比如38为2位 

    for(int d = 0; d < dnum;  d ++){//枚举每一位,共dnum趟 
        for(int i = 0; i < n; i ++){//枚举每一个数 
            int t = (a[i] / base[d]) % RADIX;//取出该位数值,即对应的桶号 
            bucket[t].push_back(a[i]);//将当前数值放入桶中(对应位) 
        }

        for(int i = 0, j = 0, k = 0; i < n; ){//i为当前元素下标,j为桶的编号
            if(k < bucket[j].size()){//k为桶中的第k号元素 
                a[i ++] = bucket[j][k ++];//依次将桶中元素存入数组(已按当前位有序) 
            }
            else j ++, k = 0;//枚举下一个桶,从该桶中第0号元素开始 
        }
        for(auto &v : bucket) v.clear();//将桶中元素清零, 开始下一趟排序 
    }
}

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;

    RadixSort(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 

优化版(不可以对负数排序)

核心代码

//基数排序 
void RadixSort(int a[], int n){
    const int RADIX = 10;//DADIX表示为十进制数 
    int maxval = a[0], minval = a[0], base[10];//base数组存的是十进制数的位权 
    vector< vector<int> > bucket(RADIX);//相当于定义10个桶 

    base[0] = 1;//个位的权值为 1 
    for(int i = 1; i < 10; i ++) base[i] = base[i - 1] * 10;//初始化权值 
    for(int i = 0; i < n; i ++){
        maxval = max(maxval, a[i]);//求出所有元素的最大值 
        minval = min(minval, a[i]);
    }

    //将所有元素右移(即映射到非负数区域) 
    if(minval < 0){
        for(int i = 0; i < n; i ++){
            a[i] -= minval;
        }
        maxval -= minval;//之前的最大值发生变化,更新原最大值 
    }

    int dnum = ceil(log10(maxval + 1));//求出最大的位数,比如38为2位 

    for(int d = 0; d < dnum;  d ++){//枚举每一位,共dnum趟 
        for(int i = 0; i < n; i ++){//枚举每一个数 
            int t = (a[i] / base[d]) % RADIX;//取出该位数值,即对应的桶号 
            bucket[t].push_back(a[i]);//将当前数值放入桶中(对应位) 
        }

        for(int i = 0, j = 0, k = 0; i < n; ){//i为当前元素下标,j为桶的编号
            if(k < bucket[j].size()){//k为桶中的第k号元素 
                a[i ++] = bucket[j][k ++];//依次将桶中元素存入数组(已按当前位有序) 
            }
            else j ++, k = 0;//枚举下一个桶,从该桶中第0号元素开始 
        }
        for(auto &v : bucket) v.clear();//将桶中元素清零, 开始下一趟排序 
    }

    //还原之前的元素序列,即将元素整体再左移回去 
    if(minval < 0){
        for(int i = 0; i < n; i ++){
            a[i] += minval;
        }
    }
}

完整代码

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

using namespace std;
const int N = 10010;

int data[N], num, idx; 

//基数排序
void RadixSort(int a[], int n){
    const int RADIX = 10;//DADIX表示为十进制数 
    int maxval = a[0], minval = a[0], base[10];//base数组存的是十进制数的位权 
    vector< vector<int> > bucket(RADIX);//相当于定义10个桶 

    base[0] = 1;//个位的权值为 1 
    for(int i = 1; i < 10; i ++) base[i] = base[i - 1] * 10;//初始化权值 
    for(int i = 0; i < n; i ++){
        maxval = max(maxval, a[i]);//求出所有元素的最大值 
        minval = min(minval, a[i]);
    }

    //将所有元素右移(即映射到非负数区域) 
    if(minval < 0){
        for(int i = 0; i < n; i ++){
            a[i] -= minval;
        }
        maxval -= minval;//之前的最大值发生变化,更新原最大值 
    }

    int dnum = ceil(log10(maxval + 1));//求出最大的位数,比如38为2位 

    for(int d = 0; d < dnum;  d ++){//枚举每一位,共dnum趟 
        for(int i = 0; i < n; i ++){//枚举每一个数 
            int t = (a[i] / base[d]) % RADIX;//取出该位数值,即对应的桶号 
            bucket[t].push_back(a[i]);//将当前数值放入桶中(对应位) 
        }

        for(int i = 0, j = 0, k = 0; i < n; ){//i为当前元素下标,j为桶的编号
            if(k < bucket[j].size()){//k为桶中的第k号元素 
                a[i ++] = bucket[j][k ++];//依次将桶中元素存入数组(已按当前位有序) 
            }
            else j ++, k = 0;//枚举下一个桶,从该桶中第0号元素开始 
        }
        for(auto &v : bucket) v.clear();//将桶中元素清零, 开始下一趟排序 
    }

    //还原之前的元素序列,即将元素整体再左移回去 
    if(minval < 0){
        for(int i = 0; i < n; i ++){
            a[i] += minval;
        }
    }
}

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;

    RadixSort(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
-86 -72 13 23 32 59 64 69 86 99