非比较排序：基数排序（radix sort）以线性时间O(n)进行排序（C++实现）

红太狼 2022-12-24 01:56 143阅读 0赞

虽然可以证明：**任何只使用 比较 的一般排序算法在最坏的情形下需要的运行时间为O(n log n)**，但是，在某些特殊情况下，以线性时间O(n)进行排序仍然是可能的：**基数排序、计数排序、和桶排序**。

### 非比较排序 ###

*  基数排序

# 基数排序 #

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog( r )m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

*  时间效率 ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配**时间复杂度为O(n)**，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。
 *  空间效率：需要2\*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

**实现方法：**

*  最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
 *  最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

int maximumGap(vector<int>& nums) {
        
            //辣鸡方法，使用快速排序，时间复杂度为O(n log n)
            // if(nums.size()<2) return 0;
            // sort(nums.begin(),nums.end());
            // int maxGap = 0;
            // for(int i = 0;i<nums.size()-1;i++){
        
            //     maxGap = max(maxGap,nums[i+1]-nums[i]);
            // }
            // return maxGap;
            int size  = nums.size();
             if(size < 2) return 0;
            //使用基数排序，非比较排序，时间复杂度为线性O(n)
            //1.首先需要知道最大数，用于控制循环
            int maxNum = *max_element(nums.begin(),nums.end());
            //2.设置基数等于1，一个作用是用于控制循环，另一个是从个位数开始找起
            int radix = 1;
            //3.制作桶的容器，用一个计数器count和一个数据暂存temp来代替
            vector<int> count(10,0);
            vector<int> temp(size);
             int i = 0,k = 0;
            //开始循环遍历
            while(radix <= maxNum){
        
                //每次循环前先将count置零
                count.assign(10,0);
                //开始遍历nums，在count中计数
                for(i = 0;i<size;i++){
        
                    k = (nums[i]/radix)%10;//当radix为1时得到的就是个位，为10时得到的是十位
                    count[k]++;
                }
                //计数完成之后，开始通过count往temp中添加数据,让count保存的数据变成temp的下标
                //count[9]的数值一定等于nums的数据成员个数
                for(i = 1;i<10;i++){
        
                    count[i] += count[i-1]; 
                }
                //为什么要将nums的数据从后往前开始放入temp? 这是为了解决某一个位上有多个数据的问题，
                //从后往前，保证了相同位数中，较大的数先放入temp，由于执行了
                //当前位数的数字按照0,1,2,3,4,5,6,7,8,9的顺序后往前添加数据count[k]--，就算两个数的k相同，后放入的较小的那个会放到较大的前面。
                for(i = size-1; i>=0;i--){
        
                    k = (nums[i]/radix)%10;
                    //比如k=9，上面说过count[9]的数值一定等于nums的数据成员个数，所以count[k]-1就是temp的最后一个数的下标
                    temp[count[k]-1] = nums[i];
                    //当前位的计数自减1，是考虑某个位置上有多个数字，比如nums有12,22，则radix为1时，count[2]一定为2
                    count[k]--;
                }
                //一遍循环过后，处理了一个位数，将temp的值赋给nums，开始下一位
                copy(temp.begin(),temp.end(),nums.begin());
                radix *=10;
            }
            //排好序了
            int maxGap = 0;
            for(int i = 0;i<nums.size()-1;i++){
        
                maxGap = max(maxGap,nums[i+1]-nums[i]);
            }
            return maxGap;
        }

#include<vector>
    #include<algorithm>
    using namespace std;
    int maxbit(int data[], int n) //辅助函数，求数据的最大位数
    {
        
        int d = 1; //保存最大的位数
        int p = 10;
        for(int i = 0; i < n; ++i)
        {
        
            while(data[i] >= p)
            {
        
                p *= 10;
                ++d;
            }
        }
        return d;
    }
    void radixsort(int data[], int n) //基数排序
    {
        
        //d为数组中最大的位数
        int d = maxbit(data, n);
        cout<<"最大位数："<<d;
    
        int *tmp = new int[n];
        int *count = new int[10]; //计数器
        int i, j, k;
        //使用LSD，从个位数开始，所以一开始基数为1
        int radix = 1;
        for(i = 1; i <= d; i++) //进行d次排序
        {
        
            for(j = 0; j < 10; j++)
                count[j] = 0; //每次分配前清空计数器
            for(j = 0; j < n; j++)
            {
        
                k = (data[j] / radix) % 10; //统计每个桶中的记录数
                count[k]++;
            }
            for(j = 1; j < 10; j++)
                count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
    
            for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
            {
        
                k = (data[j] / radix) % 10;
                tmp[count[k] - 1] = data[j];
                count[k]--;
            }
            for(j = 0; j < n; j++) //将临时数组的内容复制到data中
                data[j] = tmp[j];
            radix = radix * 10;
        }
        delete[]tmp;
        delete[]count;
    }
    int main()
    {
        
        int data []={
        73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
        for(auto x:data) cout<<x<<" ";
        cout<<endl;
        radixsort (data,sizeof(data)/sizeof(int));
        for(auto x:data) cout<<x<<" ";
        cout<<endl;
        return 0;
    }