前言:
现时同学们对“基数排序算法实现”可能比较重视,姐妹们都想要了解一些“基数排序算法实现”的相关知识。那么小编在网上收集了一些对于“基数排序算法实现””的相关内容,希望兄弟们能喜欢,兄弟们快快来了解一下吧!这是什么
基数排序有时也称为卡式排序(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;}
测试结果如下,与文字描述一致:
标签: #基数排序算法实现