龙空技术网

掌握算法-链表应用-基数排序

吃泡菜的鱼 89

前言:

现时同学们对“基数排序算法实现”可能比较重视,姐妹们都想要了解一些“基数排序算法实现”的相关知识。那么小编在网上收集了一些对于“基数排序算法实现””的相关内容,希望兄弟们能喜欢,兄弟们快快来了解一下吧!

这是什么

基数排序有时也称为卡式排序(card sort)。因为直到现代计算机出现之前,它一直用于对老式穿孔卡的排序。

如果我们有N个整数,范围是1到M(或从0到M-1),我们可以利用这个信息得到一种快速的排序叫做桶式排序(bucket sort)。我们先预设一个数组,给个名字叫Count,大小为M,并初始化为零。于是,Count有M个单元,开始时他们都是空的,当A[i]被读入时,Count[A[i]增1。在所有的输入被读进以后,扫描数组Count,打印输出排好序的表。

直白点说

这里的意思就是说,首先M的范围是包含N的,假设你有一组数组{3,2,1,7,6,4,4},假设我们有10个桶,分别是1号桶,2号桶...,...,10号桶,都是空的,我们遍历这个数组,比如第一个是3,那么我就往3号桶里放一个石子,以此类推,我们最后会有:

1号桶 - 1个石子2号桶 - 1个石子3号桶 - 1个石子4号桶 - 2个石子5号桶 - 空6号桶 - 1个石子7号桶 - 1个石子8号桶 - 空9号桶 - 空10号桶 - 空

所以当我们从1号桶开始数石子时,从1数到10,有一个石子我们就把当前桶号几下来,于是我们就会有:

1,2,3,4,4,6,7

有没有发现通过这种方式我们已经把原数组给排好序了。

一些例子

基数排序是这种方法的推广。下面举例说明一下。

设我们有10个数,范围在0到999之间,我们将其排序。一般来说,这是0到N^p-1间的N个数,p是某个常数。显然,我们不能使用桶式排序,那样桶就太多了(为了10个数的排序,我们要准备1000个桶,这里N=10, p = 3)。我们的策略是使用多趟桶式排序。这里我们使用最低有效位进行排序。

这里拿10个数的桶式排序进行举例。本例的输入是64, 8, 216, 512, 27, 729, 0, 1, 343, 125。

第一步我们按照最低优先位进行排序,也就是按个位数的大小进行排序,得到如下结果。

得到排序的结果为0,1,512,343,64,125,216,27,8,729

第二步我们按次最低有效位进行排序,也就是按十位数的大小进行排序。

得到排序的结果为0,1, 8,512,216,125,27,729,343,64。

最后一趟我们按最高位进行排序,也就是百位数。

得到排序的结果为0,1,8,27,64,125,216,343,512,729。

可以发现按照上述算法的我们的空间复杂度是N^2。

下面是代码实现:

#include <vector>#include <list>#include <iostream>#include <cmath>using std::vector;using std::list;using std::cout;using std::endl;int getNum(int n){    int i = 0;    while(n){        n = n / 10;        i++;    }    return i;   }int getLoopTimes(const vector<int> &array){    int ret = 0;    for(const auto &num : array){        int i = getNum(num);        if(i > ret){            ret = i;        }    }    return ret;}int getIndex(int num, int i){    if(i == 0){        return num % 10;    }    else{        return (int)(num / pow(10, i)) % 10;    }}void baseSort(const vector<int> &array){    int loopTimes = getLoopTimes(array); //循环次数也就是最高位数(base 10)    cout <<"循环次数:" << loopTimes << endl;    list<int> baseList;        //init baseList    for(const auto &num :  array){        baseList.emplace_back(num);    }        for(int i = 0; i < loopTimes; ++i){        list<int> listArray[10];        for(const auto &num : baseList){            const int index = getIndex(num, i);            cout << "index:" << index << endl;            listArray[index].emplace_back(num);        }        baseList.clear();        for(int i = 0; i < 10; ++i){            for(const auto &num : listArray[i]){                baseList.emplace_back(num);            }        }        for(const auto &num: baseList){            cout << num << " ";        }        cout << endl;    }}int main(){    vector<int> test = {64, 8, 216, 512, 27, 729, 0, 1, 343, 125};    baseSort(test);    return 0;}

测试结果如下,与文字描述一致:

标签: #基数排序算法实现