珠排序

十大经典排序算法

珠排序（Bead Sort）类似于算盘，每根杆子上都串有珠子，如下图所示。每行中珠子的个数表示一个数字，如果某一行中有 3 个珠子，表示该行是数字 3 。数组中最大值是几，就要准备多少根杆子。当把珠子全部串到杆子中的时候，珠子按照重力下落，就完成了排序，如下图右边部分。珠排序有一个缺点就是待排序数组中不能有负数，如果要解决有负数的问题也可以单独处理，就像前面讲位图排序的时候，让数组中所有的数字都加上一个值，把所有的数字全部变成正数即可。

private void beadSort(int[] nums) {
    // 数组长度，表示有多少行
    int length = nums.length;
    // 数组中的最大值，表示有多少列，也就是有多少根杆子
    int max = Arrays.stream(nums).max().getAsInt();
    boolean[][] bead = new boolean[length][max];// 记录珠子
    // 挂珠子
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < nums[i]; j++)
            bead[i][j] = true;
    }

    // 珠子下坠，从小到大排序。
    for (int i = 1; i < length; i++) {
        for (int j = 0; j < max; j++) {
            int line = i;
            // 从上面第 i 行开始，每列珠子只要下面有空的就往下掉落
            while (line > 0 && (bead[line - 1][j] && !bead[line][j])) {
                bead[line - 1][j] = false;
                bead[line][j] = true;
                line--;
            }
        }
    }

//        // 珠子上坠，从大往小排序
//        for (int i = 1; i < length; i++) {
//            for (int j = 0; j < max; j++) {
//                int line = i;
//                // 从上面第 i 行开始，每列珠子只要上面有空的就往上面走。
//                while (line > 0 && (bead[line][j] && !bead[line - 1][j])) {
//                    bead[line][j] = false;
//                    bead[line - 1][j] = true;
//                    line--;
//                }
//            }
//        }

    // 数珠子
    for (int i = 0; i < length; i++) {
        int j = 0;
        while (j < max && bead[i][j])
            j++;
        nums[i] = j;
    }
}

我们看到上面的步骤分为三块，先是挂珠子，然后珠子下坠，最后在数珠子。实际上我们可以把第二步省略，在挂珠子的时候每根杆子从下往上挂，这样就不需要在珠子下坠了。

private void beadSort(int[] nums) {
    // 数组长度，表示有多少行
    int length = nums.length;
    // 数组中的最大值，表示有多少列，也就是有多少根杆子
    int max = Arrays.stream(nums).max().getAsInt();
    boolean[][] bead = new boolean[length][max];// 记录珠子
    // 记录每列珠子的个数，挂珠子是从下往上的。
    int[] count = new int[max];
    // 挂珠子
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < nums[i]; j++)
            bead[length - 1 - count[j]++][j] = true;// 从小到大排序
//                bead[count[j]++][j] = true;// 从大到小排序
    }

    // 数珠子
    for (int i = 0; i < length; i++) {
        int j = 0;
        while (j < max && bead[i][j])
            j++;
        nums[i] = j;
    }
}

相关链接