惊叹数据结构之美，品味排序算法之妙：对计排、桶排的详细介绍
大家好，这里是小编的博客频道
小编的博客：就爱学编程
很高兴在ZEEKLOG这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！本文目录
引言
排序算法中的基数排序和计数排序都是非基于传统比较的排序方法，它们各自有着独特的实现原理和应用场景。下面小编将从代码实现的角度对这两种排序算法进行详细介绍。
那接下来就让我们开始遨游在知识的海洋！
正文
一、计数排序（Counting Sort）
原理概述：
计数排序是一种适用于元素范围较小的排序算法。它利用一个额外的计数数组来记录待排序数组中每个元素出现的次数，然后根据这些次数来确定每个元素在最终排序数组中的位置。
代码实现步骤：
1. 确定元素范围：找出待排序数组中的最小值和最大值，记为min和max。2. 创建计数数组：创建一个大小为max-min+1的计数数组count，用于记录每个元素出现的次数。数组的下标代表元素的值，数组的值代表该元素出现的次数。3. 统计频次：遍历待排序数组，统计每个元素出现的频率，并将该频率存储到计数数组中。4. 累计计数：将计数数组中的值进行累加，得到每个元素在最终排序数组中的位置。这个步骤确保了排序的稳定性（即相同元素的相对位置不变）。5. 构造排序结果：根据累加后的计数数组，将元素按顺序放入目标排序数组中。
示例代码：
#include<iostream>usingnamespace std;int*count_sort(int* input,int len,int min,int max){int* arr =newint[max - min +1];// 创建计数数组for(int i =0; i < max - min +1; i++) arr[i]=0;// 初始化计数数组为0// 统计每个元素的出现次数for(int i =0; i < len; i++){ arr[input[i]- min]++;}int* ans =newint[len];// 创建目标排序数组int index =0;// 用于填充目标排序数组的索引// 根据计数数组构建目标排序数组for(int i = min; i <= max; i++){for(int j =0; j < arr[i - min]; j++){ ans[index++]= i;}}return ans;// 返回排序后的数组}intmain(){int arr[]={3,6,4,5,6,3,6,4,5,5,6,4,3};int len =sizeof(arr)/sizeof(int);int* sorted_arr =count_sort(arr, len,3,6);// 输出排序结果for(int i =0; i < len; i++){ cout << sorted_arr[i]<<" ";} cout << endl;delete[] sorted_arr;// 释放动态分配的内存return0;}二、基数排序（Radix Sort）
原理概述：
基数排序又称桶排序，它通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。基数排序分为最高位优先法（MSD）和最低位优先法（LSD）。这里以最低位优先法为例进行说明。基数排序的基本思想是从数字的最低有效位开始，依次对每个数位进行一次排序。每次排序都使用稳定的排序算法（如计数排序），以保证排序后元素的相对位置不变。经过多次排序后，整个数列就变得有序了。
代码实现步骤：
1. 获取最大位数：找出待排序数组中所有数字的最大位数。2. 逐位排序：从最低有效位开始，依次对每个数位进行排序。每次排序都使用计数排序算法。3. 合并结果：由于每次排序都是稳定的，所以可以直接在原数组上进行操作，无需额外的合并步骤。
示例代码（以最低位优先法为例）：
#include<iostream>#include<vector>#include<algorithm>#include<cmath>usingnamespace std;// 获取数字d在第pos位的值（0~9）intgetDigit(int d,int pos){return(d /static_cast<int>(pow(10, pos)))%10;}// 对数组arr按照第pos位进行计数排序voidcountingSortByDigit(vector<int>& arr,int pos){constint radix =10;// 基数为10（因为是十进制数） vector<int>output(arr.size());// 存储排序结果的数组 vector<int>count(radix,0);// 计数数组// 统计每个数字在第pos位上出现的次数for(int num : arr){int digit =getDigit(num, pos); count[digit]++;}// 修改count数组，使其包含实际位置信息for(int i =1; i < radix; i++){ count[i]+= count[i -1];}// 构建输出数组for(int i = arr.size()-1; i >=0; i--){int digit =getDigit(arr[i], pos); output[count[digit]-1]= arr[i]; count[digit]--;}// 将排序结果复制回原数组copy(output.begin(), output.end(), arr.begin());}// 基数排序主函数voidradixSort(vector<int>& arr){if(arr.empty())return;// 找到最大数的位数int maxNum =*max_element(arr.begin(), arr.end());int maxDigits =log10(maxNum)+1;// 从个位开始，逐位进行计数排序for(int pos =0; pos < maxDigits; pos++){countingSortByDigit(arr, pos);}}intmain(){ vector<int> arr ={170,45,75,90,802,24,2,66};radixSort(arr);// 输出排序结果for(int num : arr){ cout << num <<" ";} cout << endl;return0;}三、总结
- 计数排序：适用于元素范围较小的情况，时间复杂度为O(n+k)，其中n是待排序元素的个数，k是元素的范围。空间复杂度高，需要额外的计数数组。
- 基数排序：通过逐位排序来实现整体排序，通常使用计数排序作为子过程。时间复杂度为O(d*(n+r))，其中d是数字的最大位数，n是待排序元素的个数，r是基数（对于十进制数，r=10）。基数排序是稳定的排序算法。
