基数排序

joe

1、基数排序简要概述

（1）基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucketsort）或binsort，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。

（2）将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

————————————————

主体内容来自：https://blog.csdn.net/itcsdn_/article/details/108287824

public class test {

    public static void main(String[] args) {

        int array[] = new int[]{20, -1, -18, 101, 319, 88};

        System.out.print("基数(桶)排序前：");

        for (int i = 0; i < array.length; i++) {

            System.out.print(array + " ");

        }

        //因为有负数，所以先找到最小数(-18);

        int min = array[0];

        for (int i = 0; i < array.length; i++) {

            if (min > array) {

                min = array;

            }

        }

        //数组所有数据都减去该值

        for (int i = 0; i < array.length; i++) {

            array = array - min;

        }

        radixSort(array);

        //按正整数排序，最后数组所有数据加上原最小数(-18)

        for (int i = 0; i < array.length; i++) {

            array = array + min;

        }

        System.out.println();

        //进过排序后，要在该数组的基础上，加上最小值

        System.out.print("基数(桶)排序后：");

        for (int i = 0; i < array.length; i++) {

            System.out.print(array + " ");

        }

    }

    public static void radixSort(int a[]) {

        //用二维数组来表示桶

        int bucket[][] = new int[10][a.length];

        //用一维数组来表示桶中元素的个数

        //比如eleCounts[0]记录第0个桶中元素的个数

        int eleCounts[] = new int[10];

        int max = a[0];

        for (int i = 1; i < a.length; i++) {

            if (a > max) {

                max = a;

            }

        }

        int maxLength = (max + "").length(); //记录最大数的位数

        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {

            for (int j = 0; j < a.length; j++) {

                int digit = a[j] / n % 10;

                bucket[digit][eleCounts[digit]] = a[j];

                eleCounts[digit]++;

            }

            int index = 0;

            for (int k = 0; k < eleCounts.length; k++) {

                if (eleCounts[k] != 0) {

                    for (int l = 0; l < eleCounts[k]; l++) {

                        a[index++] = bucket[k][l];

                    }

                }

                eleCounts[k] = 0;

            }

        }

    }

}