【数据结构与算法】基数排序算法(桶排序)的介绍和程序实现、二分查找算法(折半查找)查找有序序列的多个相同数值

1. 基数排序算法 1.1 基数排序的介绍

基数排序(Radix Sort)是桶排序的扩展。基数排序属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort)或bin sort

基数排序法是属于稳定性的排序，而且效率特别高，但是特别占用内存空间，数据量大容易造成内存溢出。稳定性是指当两个相同的元素，进行排序后，它们的次序并不会发现变化

基数排序基本思想：将所有待比较整数数值统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始，按最低位将要排序的元素分配至对应的”桶“中，进行一次排序，可以保证数据的低位顺序在后面的高位排序中是有序的。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。注意基数排序不支持负整数，如果要支持则需要进行拓展

1.2 基数排序的程序实现

需求：有一组无序的数据{53, 3, 542, 748, 14, 214}，请用基数排序算法实现从小到大排列。因最大的数到百位，所有需要进行3轮排序

步骤如下：

1. 第1轮排序(按照个位排序)： 事先准备10个数组(10个桶)， 0-9号桶分别对应个位数的0-9。将各个数，按照个位数大小放入到对应的各个桶中。然后依次从0-9号桶，按照加入元素的先后顺序取出，再将桶中的数据清空。第1轮排序后顺序为：{542, 53, 3, 14, 214, 748}
2. 第2轮排序(按照十位排序)：将各个数，按照十位数大小放入到对应的各个桶中 。然后依次从0-9号桶，按照加入元素的先后顺序取出，再将桶中的数据清空。第2轮排序后顺序为：{3, 14, 214, 542, 748, 53} 3. 第3轮排序(按照百位排序)：将各个数，按照百位数大小放入到对应的各个桶中。然后依次从0-9号桶，按照加入元素的先后顺序取出，再将桶中的数据清空。第3轮排序后顺序为：{3, 14, 53, 214, 542, 748}。此时排序完成 程序如下：

import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        int[] array = {53, 3, 542, 748, 14, 214};

        radixSort(array);

        System.out.println("基数排序后 " + Arrays.toString(array));
    }

    // 基数排序方法实现
    public static void radixSort(int[] array) {
        // 得到数组中的最大数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        // 得到最大数的位数
        int maxLength = (max + "").length();

        // 定义一个二维数组
        // 第一个维度表示桶，0-9号桶分别对应位数0-9
        // 第二个维度用于储存每个桶对应的数据，大小为原数组的大小，以防所有数的同一位数都一样
        int[][] bucket = new int[10][array.length];

        // 定义一个数组，数组的index和桶的号对应，数组index对应的值就是对应桶中保存元素的个数
        int[] bucketElementCounts = new int[10];

        // 最大数有多少位，就需要进行多少次排序
        // n用于计算每个数对应位数的值
        for (int i = 1, n = 1; i