淮安软件园有做网站的吗,宁波网站seo,搜狐快站做淘宝客网站,偃师建设局网站计数排序与基数排序
计数排序
计数排序#xff1a;使用一个数组记录序列中每一个数字出现的次数#xff0c;将该数组的下标作为实际数据#xff0c;元素的值作为数据出现的次数。例如对于序列[3,0,1,1,3,3,0,2]#xff0c;统计的结果为#xff1a;
0出现的次数#xf…计数排序与基数排序
计数排序
计数排序使用一个数组记录序列中每一个数字出现的次数将该数组的下标作为实际数据元素的值作为数据出现的次数。例如对于序列[3,0,1,1,3,3,0,2]统计的结果为
0出现的次数2次
1出现的次数2次
2出现的次数1次
3出现的次数3次依据出现的次数就可以构建出排序之后的序列
void CountSort(vectorint nums) {int minNum nums.front();int maxNum nums.front();for (int num : nums) {minNum std::min(minNum, num);maxNum std::max(maxNum, num);}int helpSize maxNum - minNum 1;int* help new int[helpSize] {0};//例如最大值为10最小值为5需要开辟的数组大小是10-51for (int num : nums) {help[num - minNum];//统计次数}nums.clear();for (int i 0; i helpSize; i) {while (help[i]--) {nums.push_back(i minNum);}}delete[] help;
}计数排序的时间复杂度和空间复杂度 时间复杂度O(Nmax-min)其中max为数组中的最大元素min为数组中的最小元素。计数排序需要遍历原数组一趟得到原数组的最大值和最小值从而决定需要开辟的辅助数组的大小还需要遍历辅助数组得到有序序列
空间复杂度O(max-min)取决于数组中最大值和最小值的差
计数排序适用于数据量很大但是数据分布比较密集的场景例如有1亿个数它们都在[20,1000]范围此时就可以使用计数排序与其它排序算法相比例如快排、冒泡计数排序是一种非比较排序
基数排序
在计数排序中对于数据较为分散的场景所需开辟的额外空间较大例如序列[1,56,26,9999,7]若使用计数排序需要额外开辟一个大小为9999的数组但是原数组只有5个数需要进行排序在这种情况下可以考虑使用基数排序
基数排序也是一种非比较排序基本思想是先将原序列按照个位进行排序在按照十位进行排序……依次类推直到序列完全有序以[1,56,26,9999,7]为例流程如下 基数排序的轮数取决于序列中最大值的位数在进行基数排序时位数小的数字一定在位数大的数字的前面例如上图中7虽然在进行第一轮排序完成后处于56的后面但是当完成第二轮排序后7处于56的前面因为7的十位为0 如何提取一个数字的个位、十位、百位 方案一使用to_string将该数字转化为字符串依次进行提取
方案二定义一个offset变量初始为1将(num/offset)%10得到个位每进行一轮将offset*10
int num 3675;
int offset 1;
int bitNum;
while (bitNumnum / offset) {cout bitNum % 10 ;offset * 10;
}
cout endl;基数排序的桶 在进行基数排序时一般使用队列作为基数排序的桶对10进制数字进行排序就需要准备9个队列
void RadixSortByQueue(vectorint nums, int bits, int BASE 10) {//使用队列作为桶进行基数排序//bits表示序列中的最大值的位数//BASE表示多少进制vectorqueueint Queues;Queues.resize(BASE);int offset 1;for (int offset 1; bits 0; bits--, offset * BASE) {//例如最大值为156则进行3轮for (int num : nums) {int bitNum (num / offset) % BASE;//得到个位/十位/百位……的数Queues[bitNum].push(num);}//按照个位/十位/百位……排好的数已经放入Queues中nums.clear();for (auto Queue : Queues) {while (!Queue.empty()) {nums.push_back(Queue.front());Queue.pop();}}}
}基数排序的优化 前缀数量分区以序列[1,56,26,9999,7]为例个位数分别是1,6,6,9,7可以得到的前缀信息如下
个位数1的数据数量:1
个位数6的数据数量:3
个位数7的数据数量:4
个位数9的数据数量:5那么在每一轮按照特定位进行排序时就不需要使用队列直接开一个和原始数组等规模的辅助数组help即可将[1,56,26,9999,7]按照个位进行排序对于数字7个位为7由于个位数7的数据数量是4所以7直接放到help数组中下标为3的位置此时原序列中的7已经放到help数组中原序列中个位数7的数据数量减少一个变为3以此类推直到原序列中的数据全部按照规则转移到help数组中此时help数组中的数据就是按照位排序好的数据
void RadixSort(vectorint nums, int bits, int BASE 10) {//bits表示序列中的最大值的位数//BASE表示多少进制int* counts new int[BASE] {0};int* help new int[nums.size()]{ 0 };int offset 1;for (int offset 1; bits 0; bits--, offset * BASE) {memset(counts, 0, sizeof(int) * BASE);for (int num : nums) {int bitNum (num / offset) % BASE;counts[bitNum];//先统计个数}for (int i 1; i BASE; i) {counts[i] counts[i - 1];//统计前缀数量}for (int i nums.size() - 1; i 0; i--) {int bitNum (nums[i] / offset) % BASE;help[--counts[bitNum]] nums[i];}memcpy(nums.data(), help, sizeof(int) * nums.size());}delete[] help;delete[] counts;
}为什么需要从后往前遍历向help数组中填数据
以[1,99,7]为例在排个位数时可以从后往前也可以从前往后没有影响个位数排完之后得到[1,7,99]但是在排十位数时必须从后往前否则就会打乱1和7的顺序因为1和7的十位都是0十位0的数的个数是2,7是最后一个十位的数因此在遍历时需要从后往前遍历排到靠后位置. 基数排序的拓展 如果原序列中存在负数如何进行基数排序
将原序列中的所有数字加上最小值的绝对值在进行基数排序将排完序的结果在减去原来最小值的绝对值。如果存在溢出问题需要考虑使用long long类型。
void RadixSortContainMinus(vectorint nums, int BASE 10) {int minNum nums[0];for (int num : nums) {minNum std::min(minNum, num);}int maxNum 0;for (int num : nums) {num - minNum;maxNum std::max(maxNum, num);}int bits 1;while (maxNum / BASE) {bits;maxNum / BASE;}RadixSort(nums, bits, BASE);for (int num : nums) {num minNum;}
}如果需要排序的数字不是十进制如何使用基数排序实现
若需要排序的数字不是10进制只需要修改BASE即可其它思路一致例如需要排序的数字是16进制那么counts数组的大小定为16即可统计每一位在0~f的数量依然使用前缀分区技巧 基数排序的时间复杂度 基数排序的时间复杂度为O(m*n)其中m表示原序列中最大值的位数n表示数据量因为要根据位数确定排多少轮。基数排序的空间复杂度为O(mn)需要使用一个help数组和一个counts数组其中counts数组用于统计个数help数组用于进行保存这一轮排序完毕的数据.
