排序算法-基数排序

编程知识更新时间:2023-05-02 12:10:30

排序算法-基数排序

算法思想

基数排序是采用多关键字排序思想（即基于关键字各位的大小进行排序地），借助“分配”、“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先(MSD)【降序】排序和最低位优先(LSD)【升序】排序。

以r为基数的最低位优先基数排序过程：假设线性表是由节点序列 a 0 , a 1 . . . a n − 1 a_{0}, a_{1}...a_{n-1} a0,a1...an−1构成，每个节点 a j a_{j} aj的关键字由 d d d元组 ( k j d − 1 , k j d − 2 , . . . , k j 1 , k j 0 ) (k^{d-1}_{j}, k^{d-2}_{j},...,k^{1}_{j},k^{0}_{j}) (kjd−1,kjd−2,...,kj1,kj0)组成，其中 0 < = k j i < = r − 1 0<=k^{i}_{j}<=r-1 0<=kji<=r−1(0<=j<n,0<=i<=d-1)。

这段话要如何理解呢？以十进制数排序为例。其基数就为 0 0 0~ 9 9 9，r=10，假设线性表中一个元素的数值为384，该关键字就由3元组 ( 3 , 8 , 4 ) (3,8,4) (3,8,4)组成，即由百位、十位、个位组成，其d值就为3。

在排序的过程中，需要使用r个队列 Q 0 , Q 1 , . . . , Q r − 1 Q_{0},Q_{1},...,Q_{r-1} Q0,Q1,...,Qr−1。排序过程如下：

分配：开始时，把 Q 0 , Q 1 , . . . , Q r − 1 Q_{0},Q_{1},...,Q_{r-1} Q0,Q1,...,Qr−1各个队列置为空队列，然后依次考察线性表中的每一个结点 a j a_{j} aj，如果 a j a_{j} aj的关键字 k j i = k k^{i}_{j}=k kji=k，就把 a j a_{j} aj放入 Q k Q_{k} Qk队列中。

收集：把 Q 0 , Q 1 , . . . , Q r − 1 Q_{0},Q_{1},...,Q_{r-1} Q0,Q1,...,Qr−1各个队列中的结点首尾相接，得到新的结点序列，从而组成新的线性表。

基数排序的过程

降序：基数从小到大收集

升序：基数从大到小收集。

基数排序完整代码实现（升序）：

package com.sort;

import java.util.LinkedList;
import java.util.Queue;

public class BaseSort {
    public static void main(String[] args) {
        int[] nums = {3,89,4,53,6,825,900,0,1000,53};
        basesort(nums,nums.length);
        System.out.println("最终输出结果:");
        for(int num:nums){
            System.out.print(num+" ");
        }


    }
    public static void basesort(int[] nums,int len){
        int max = 0; //寻找待排序数组中的最大值，以确定位数d
        for(int num:nums)
            max = Math.max(max,num);
        int d = GetNum_d(max);
        //建立分配和收集队列,十进制数总共需要0~9，十个队列
        Queue<Integer>[] queues = new Queue[10];
        //初始化这10个队列
        for(int i=0;i<10;++i){
            queues[i] = new LinkedList<>();
        }
        //根据位数d来确定 分配和收集 的趟数
        for(int i=0;i<d;++i){
            //分配
            for(int num:nums){
                int temp = num;
                num /= (int)Math.pow(10,i);
                queues[num%10].offer(temp);
            }
            //收集,降序排列所以从最低位开始收集
            int k = 0;
            for(int j=0;j<10;++j){
                while(!queues[j].isEmpty() && k<len){
                    nums[k++] = queues[j].poll();
                }
            }
            System.out.printf("第 %d 趟收集之后的结果:\n",i);
            for(int num:nums){
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
    public static int GetNum_d(int num){
        int d = 1;
        while(num/10!=0){
            num /=10;
            d++;
        }
        return d;
    }

}

输出结果：

复杂度分析

主要针对上述代码实现，不同语言分析会有所不同。

时间复杂度
一趟分配的时间复杂度为 O ( n ) O(n) O(n)，一趟收集的时间复杂度为 O ( r + n ) O(r+n) O(r+n)，总共需要d趟分配收集，时间复杂度为 O ( d ( 2 n + r ) ) O(d(2n+r)) O(d(2n+r))，即 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)).