Java中8种常见的排序方法(8)

// 求得最大位数d
    public static int getMaxWeishu(int[] a) {
        int max = a[0];
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max)
                max = a[i];
        }
        int tmp = 1, d = 1;
        while (true) {
            tmp *= 10;
            if (max / tmp != 0) {
                d++;
            } else
                break;
        }
        return d;
    }

// pos=1表示个位,pos=2表示十位
    public static int getNumInPos(int num, int pos) {
        int tmp = 1;
        for (int i = 0; i < pos - 1; i++) {
            tmp *= 10;
        }
        return (num / tmp) % 10;
    }

private static int[] radixSort(int[] data, int d) {
        int[][] array = new int[10][data.length + 1];
        for (int i = 0; i < 10; i++) {
            array[i][0] = 0;
            // array[i][0]记录第i行数据的个数
        }
        for (int pos = 1; pos <= d; pos++) {
            for (int i = 0; i < data.length; i++) {
                // 分配过程
                int row = getNumInPos(data[i], pos);
                int col = ++array[row][0];
                array[row][col] = data[i];
            }
            for (int row = 0, i = 0; row < 10; row++) {
                // 收集过程
                for (int col = 1; col <= array[row][0]; col++) {
                    data[i++] = array[row][col];
                }
                array[row][0] = 0;
                // 复位,下一个pos时还需使用
            }
        }
        return data;
    }

private static void mergeSort(int[] data, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            mergeSort(data, low, mid);
            // 右边
            mergeSort(data, mid + 1, high);
            // 左右归并
            merge(data, low, mid, high);

}

}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/e3c7ef191ec5f9cba3335d3d026fea11.html