排序（八）— 基数排序

基数排序的基本思想：
是桶排序的扩展，我们需要给待排序记录准备10个桶，为什么是10个？？因为一个数的任何一位上，其数字大小都位于0~9之间，因此采用10个桶，桶的编号分别为0,1,2,3,4...9，对应待排序记录中每个数相应位的数值，基数排序也是因此而得名。

/**
 * FileName: RadixSort
 * Author:   Sandy
 * Date:     2018/12/8 14:25
 * Description: 基数排序
 * Version: v1.0.0
 */

package SortDemo;

public class RadixSort {

    public static int getMax(int [] list){
        int temp = list[0];
        for(int i=1; i<list.length; i++){
            if(temp<list[i])
                temp = list[i];
        }
        return temp;
    }

    public static void BitSort(int[] list, int bit){

        int index;
        int count [] = new int[10];
        int temp [] = new int[list.length];

        //计数
        for (int i=0; i<list.length;i++){
            index = (list[i]/bit)%10;
            count[index]++;
        }

        //找到每一个数在temp表中的位置
        for (int j=1; j<count.length; j++){
            count[j] += count[j-1];
        }

        //排序
        for(int i=0; i<list.length; i++){
            index = (list[i]/bit)%10;
            temp[list.length-count[index]] = list[i];
            count[index]--;
        }

        for (int i=0; i<list.length; i++)
            list[i] = temp[i];
    }

    public static  void RadixSort(int [] list){

        int max = getMax(list);

        for(int exp=1; max/exp>0; exp *= 10){
            BitSort(list, exp);
        }

    }

    public static void main(String[] args) {
        int [] list = {3,14,21,47,168,19,21,107};

        System.out.print("before sort: ");
        for (int i = 0; i < list.length; i++)
            System.out.printf("%d ",list[i]);
        System.out.println();

        RadixSort(list);

        System.out.print("after sort: ");
        for (int i = list.length-1; i >= 0; i--)
            System.out.printf("%d ",list[i]);
        System.out.println();
    }

}

基数排序时间复杂度
假设被排序的数列中有N个数，基数排序的时间复杂度是O(N*digit)。数组中最大的数是digit位数。

基数排序稳定性
归并排序是稳定的算法，它满足稳定算法的定义