排序--基数排序

一、不基于比较的排序算法

1.1、计数排序

这是一种另类排序，它不是基于比较的排序算法。比较小众，根据数据的分布情况，即频率。

1.2、基数排序

数据结构不统一，一般采用队列，先进先出。

比如[13,17,26,72,100],先找最高位有几位，有3位，进行补齐
|
|
↓
[013,017,026,072,100],然后对每位准备一个队列，从个位开始存放
|
|
↓
0位队列存放：100 2位队列存放：072 3位队列存放：013 6位队列存放：026 7位队列存放：017
然后依次从左到右取出数据
|
|
↓
[100,072,013,026,017]，然后准备十位队列，同理
|
|
↓
0位队列存放：100 1位队列存放：013 017 2位队列存放：026 7位队列存放：072
然后依次从左到右取出数据
|
|
↓
[100,013,017,026,072],同理百位
|
|
↓
0位队列存放：013，017，026，072 1位队列存放：100
然后依次从左到右取出数据
[013,017,026,072,100]有序

理由：

1. 基数排序是基于计数排序的扩展，是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
   要求：
   
   要排序的东西必须要有进制，比如十进制、二进制等。
   
   核心点:
   
   按位分配收集

// 大致情况如下：voidradixSort(vector<int>&nums){if(nums.empty()||nums.size()<2)return;radixSort(nums,0,nums.size()-1,maxBits(nums));}staticintmaxBits(constvector<int>&nums){if(nums.empty())return0;intmaxVal=INT_MIN;for(intnum:nums){maxVal=max(num,maxVal);}// 处理最大值为0的情况if(maxVal==0)return1;intres=0;// 处理负数：取绝对值inttemp=abs(maxVal);while(temp!=0){res++;temp/=10;}returnres;}

基数排序的实现

// digit: 最大位数staticvoidradixSortImpl(vector<int>&nums,intbegin,intend,intdigit){constintradix=10;// 基数，这里是十进制inti=0,j=0;// 辅助数据，用于存储排序结果vector<int>bucket(end-begin+1);// 对每一位进行排序for(intd=1;d<=digit;++d){// 计数数组，记录每个数字出现的次数vector<int>count(radix,0);// 统计当前位上每个数字出现的次数for(i=begin;i<=end;++i){j=getDigit(nums[i],d);count[j]++;}// 将计数转换为前缀和，表示每个数字在输出数组中的最后位置// 注意：这里从 i=1 开始累加，count[0] 保持不变for(i=1;i<radix;++i){count[i]+=count[i-1];}// 从后向前遍历，保持稳定性for(i=end;i>=begin;--i){j=getDigit(nums[i],d);// count[j] - 1 是当前数字应该放入的位置bucket[count[j]-1]=nums[i];count[j]--;}// 将桶中的数据复制回原数组for(i=begin,j=0;i<=end;++i,++j){nums[i]=bucket[j];}}}

获取数字x的第d位数（从个位开始，d=1表示个位）

staticintgetDigit(intx,intd){// 处理负数：先取绝对值intnum=abs(x);// 计算第d位的数字return(num/static_cast<int>(pow(10,d-1)))%10;}// 基数排序的入口函数voidradixSort(vector<int>&nums){if(nums.empty()||nums.size()<2)return;// 获取最大位数intdigit=maxBits(nums);// 调用实际的排序函数radixSortImpl(nums,0,nums.size()-1,digit);// 处理负数：将负数放到数组前面// 基数排序通常不能直接处理负数，需要特殊处理// 先处理正数部分，再处理负数部分}

处理负数的基数排序版本

voidradixSortWithNegative(vector<int>&nums){if(nums.empty()||nums.size()<2)return;// 分离正数和负数vector<int>negatives,positives;for(intnum:nums){if(num<0){negatives.push_back(-num);// 转换为正数处理}else{positives.push_back(num);}}// 分别排序radixSort(positives);radixSort(negatives);// 合并结果：先放负数（从大到小），再放正数intindex=0;// 负数要恢复为负数，并且因为我们对绝对值排序了，所以需要反转for(inti=negatives.size()-1;i>=0;--i){nums[index++]=-negatives[i];}// 正数直接放入for(intnum:positives){nums[index++]=num;}}

二、实操演练

2.1、以LeetCode 164为例

题目描述:

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例1：

输入: nums = [3,6,9,1]

输出: 3

解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3

解题思路:

1. 题目要求时间复杂度在线性时间内，就等同于O(n)，所以不能使用O(nlogn)的排序算法，比如快速排序、归并排序、堆排序等。
   
2. 那么基数排序刚好满足时间复杂度O(n)
3. 可以先排序数组，然后遍历排序后的数组，计算相邻差值并找出最大值。

classSolution{public:intmaximumGap(vector<int>&nums){if(nums.size()<2)return0;intret=0;radixSort(nums);for(inti=0,j=1;j<nums.size();i++,j++){ret=std::max(ret,abs(nums[i]-nums[j]));}returnret;}staticintmaxBits(constvector<int>&nums){if(nums.empty())return0;intmaxVal=INT_MIN;for(intnum:nums){maxVal=max(num,maxVal);}// 处理最大值为0的情况if(maxVal==0)return1;intres=0;// 处理负数：取绝对值inttemp=abs(maxVal);while(temp!=0){res++;temp/=10;}returnres;}staticvoidradixSortImpl(vector<int>&nums,intbegin,intend,intdigit){constintradix=10;// 基数，这里是十进制inti=0,j=0;// 辅助数据，用于存储排序结果vector<int>bucket(end-begin+1);// 对每一位进行排序for(intd=1;d<=digit;++d){// 计数数组，记录每个数字出现的次数vector<int>count(radix,0);// 统计当前位上每个数字出现的次数for(i=begin;i<=end;++i){j=getDigit(nums[i],d);count[j]++;}// 将计数转换为前缀和，表示每个数字在输出数组中的最后位置// 注意：这里从 i=1 开始累加，count[0] 保持不变for(i=1;i<radix;++i){count[i]+=count[i-1];}// 从后向前遍历，保持稳定性for(i=end;i>=begin;--i){j=getDigit(nums[i],d);// count[j] - 1 是当前数字应该放入的位置bucket[count[j]-1]=nums[i];count[j]--;}// 将桶中的数据复制回原数组for(i=begin,j=0;i<=end;++i,++j){nums[i]=bucket[j];}}}// 获取数字x的第d位数（从个位开始，d=1表示个位）staticintgetDigit(intx,intd){// 处理负数：先取绝对值intnum=abs(x);// 计算第d位的数字return(num/static_cast<int>(pow(10,d-1)))%10;}// 基数排序的入口函数voidradixSort(vector<int>&nums){if(nums.empty()||nums.size()<2)return;// 获取最大位数intdigit=maxBits(nums);// 调用实际的排序函数radixSortImpl(nums,0,nums.size()-1,digit);}};

虽然能pass了，但基本思想还是要将数组进行完全排序之后，再重新计算一遍相邻差值，为了找最大间隔而完成了全部排序；其实，我们只需要找到最大间隔，不需要完全排序，所以可以优化一下，只对最大间隔的元素进行排序，这样时间复杂度会变得更低，虽然都是O(n)。