排序算法 - 珠排序

基本思想

将每个数用珠子表示，例如：数字5就是5个珠子。用珠子表示好每一个数后，让所有的珠子自由下落。排序完成。

上图中的三个珠就表示数字3,两个珠表示数字2,这个OK了继续,这里的3和2都叫bead。

上图(a)中有两个数字,4和3,分别串在四条线上,于是数字4的最后一个珠子下落,因为它下边是空的,自由下落后变成上图(b)

上图(c)中随机给了四个数字,分别是3,2,4,2,这些珠子自由下落,就变成了(d)中,落完就有序了,2,2,3,4

以上就是珠排序的精华。

上图中的n表示待排序数组的长度,有多少数字就有多少层,横向表示一层;m表示有多少个珠子,就是多少个1,这取决于最大数是几。

举个例子：比如待排数组[6 2 4 1 5 9]。

让珠子全部做自由落体运动

9没有什么好落的,它在最底层

5也没有什么好落的,全部有支撑点

1同样不需要滑落

4除了第一个珠子不动外,其它三颗全部下落,落到1的位置变成下边这样

过程的细节不画了,原则就是你下边有支点,你就不用再滑落了,最后变成下边这样,排序完毕。

从上到下顺序输出即可得到结果:[ 1 2 4 5 6 9]。

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 珠排序:将每个数用珠子表示，例如：数字5就是5个珠子。用珠子表示好每一个数后，让所有的珠子自由下落。排序完成。
 */
public class BeadSort {

    /**
     * 珠排序
     *
     * @param unsorted 待排序列
     * @return
     */
    public static int[] beadSort(int[] unsorted) {
        //待排序列中的最大值
        int max = 0;
        //获取最大值
        for (int i = 0; i < unsorted.length; i++) {
            if (unsorted[i] > max) {
                max = unsorted[i];
            }
        }
        //每个数都用珠子表示，比如5就用5个珠子，所以用二维数组表示每个数
        char[][] grid = new char[unsorted.length][max];
        int[] levelCount = new int[max];
        for (int i = 0; i < max; i++) {
            levelCount[i] = 0;
            for (int j = 0; j < unsorted.length; j++) {
                grid[j][i] = '_';
            }
        }
        //删除珠子
        for (int i = 0; i < unsorted.length; i++) {
            int num = unsorted[i];
            for (int j = 0; num > 0; j++) {
                grid[levelCount[j]++][j] = '*';
                num--;
            }
        }
        //数珠子，放到已排序列表
        int[] sorted = new int[unsorted.length];
        for (int i = 0; i < unsorted.length; i++) {
            int putt = 0;
            for (int j = 0; j < max && grid[unsorted.length - 1 - i][j] == '*'; j++) {
                putt++;
            }
            sorted[i] = putt;
        }
        return sorted;
    }

    public static void main(String[] args) {
        //产生随机待排序列
        int[] unsorted = new int[(int) (Math.random() * 11) + 5];
        for (int i = 0; i < unsorted.length; i++) {
            unsorted[i] = (int) (Math.random() * 10);
        }
        System.out.println("**************珠排序******************");
        System.out.println("排序前：");
        CommonUtils.display(unsorted);
        System.out.println("排序后：");
        int[] sorted = beadSort(unsorted);
        CommonUtils.display(sorted);
    }
}

测试结果如下