基数排序 ---------------- JAVA实现

基数排序

---

• 基数排序（radix sort），又称为“桶子排序法（bucket sort）”。
  基本思想：
  将所有待比较的元素数值（正整数）统一为同样的数位长度，数位较短的元素在前面补零占位。然后，从最低位开始，依次进行每一趟排序，直到最高位排序完成，则整个数列就成为一个有序的序列。

---

算法分析

现在，我们来对具体的排序过程进行详细分析：

假设待排序数组为一个整型数组：

int[] a = {542, 3521, 13459, 852, 742, 46, 2, 1, 633, 32}

首先，我们需要找到数组中的最大数，在a数组中最大数即为13459，一个五位正整数。也就是说，整个排序需要进行5趟。然后，我们需要对除最大数外的其他数进行用零补位，得到的数组可看作

int[] a = {00542, 03521, 13459, 00852, 00742, 00046, 00002, 00001, 0633, 0032}

接下来，我们需要用从最低位（个位）开始进行排序。在每一趟排序过程中，我们将中间数据，暂时装入从0-9编号的十个“桶”中，如下图所示。

对数组进行遍历，根据元素个位数值，将元素装进从0-9编号的相应的桶中。再遍历list这个二维数组，得到本趟排序（个位）后的数组：

int[] a = {3521，1，542，852，742，2，32，633，46，13459}

如此重复，直到最高位排序完成，该数组就变成有序的数组了。

实现步骤总结

• Step 1
  在带排序的数组中，找到最大数，并判断最大数的位数；
• Step 2
  建立一个二维数组，用于存放从最低位到最高位排序过程中的中间结果；
• Step 3
  针对每一趟的排序，进行元素的分配和收集。

代码实现

import java.util.ArrayList;
import java.util.List;

public class radixSort {
    public static void main(String[] args) {
        int[] a = {542, 3521, 13459, 852, 742, 46, 2, 1, 633, 32};
        System.out.println("Before Sort the Array is:");
        for (int array : a
                ) {
            System.out.print(array + " ");
        }
        // 调用基数排序
        myRadixSort(a);
        System.out.println();
        System.out.println("After Sort the Array is:");
        for (int array : a
                ) {
            System.out.print(array + " ");
        }
    }

    public static void myRadixSort(int[] arr) {
        int max = 0;
//        找到最大的数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
//        获取最大数的位数
        int times = 0;
        while (max > 0) {
            max = max / 10;
            times++;
        }


//        创建一个二维的list
        List<ArrayList> list = new ArrayList<>();
//  创建10个list（每一位有从0到9，一共10个数，每个list数组用来存放每次迭代中，0-9 每个数组中需要装入的数）
        for (int i = 0; i < 10; i++) {
            ArrayList list1 = new ArrayList();
 //在二维数组中把这10个数组加进去，相当于二维数组的行，从0-9的行
            list.add(list1);           
        }


//        进行times次分配和收集
        for (int i = 0; i < times; i++) {
//            分配
            for (int j = 0; j < arr.length; j++) {
                int x = arr[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
    // list.get(x) 是在返回第0的这个行的list上面的数，然后再 add(arr[j]) 是把当前的这个数添加到末尾去
                list.get(x).add(arr[j]);                  
            }




//            收集        ------------>   把这0-9共10个list里面的数值存到一个数组里面
            int count = 0;
            for (int j = 0; j < 10; j++) {
                while (list.get(j).size()>0){
            // 把list这个二维list中的第j行返回并赋值给list2
                    ArrayList<Integer> list2 = list.get(j);    
            //  把list2这个数组中的第0个位置的元素，赋值给arr[count]         
                    arr[count] = list2.get(0);   
           //   把list2这个数组中的第0个位置的元素删除掉，则后面的元素会自动移上来                      
                    list2.remove(0);                            
                    count++;                                            
                }
            }
        }
    }