Rank Sort in Java -Yuan.

Rank Sort

算法描述

一组数，从第一个开始，遍历整个数组，记录小于这个数的元素个数，这个元素个数就是新数组中第一个数的地址。以此类推，直到最后一个数。这样就得到一个新的排序好的数组（升序）

时间复杂度
O(n^2)

代码实现

• 一维数组

public class project1_RankSort {
    public static void main(String[] args) {
        int[] testA = { 1, 62, 81, 0, 23, 55, 76, 87, 20, 54, 65, 76, 1 };

        // print the initial array;
        System.out.println("The initial one-dimensional array is:");
        for (int i = 0; i < testA.length; i++) {
            System.out.print(testA[i] + " ");
        }
        System.out.println();

        testA = RankSort(testA);

        // print the finished array;
        System.out.println("The sorted one-dimensional array is:");
        for (int i = 0; i < testA.length; i++) {
            System.out.print(testA[i] + " ");
        }
        System.out.println();

    }

    public static int[] RankSort(int[] a) {
        int[] arr = new int[a.length]; // Defined a new array to be the sorted array;
        for (int i = 0; i < a.length; i++) {
            int index = 0; // Defined an index variable which is the index of the integer in new array;

            // Find how many integers smaller than a[i], the number of them is the index of
            // a[i] in new array;
            for (int j = 0; j < a.length; j++) {
                if (a[i] > a[j]) {
                    index++;
                }
            }
            arr[index] = a[i];
        }

        /*
         * To avoid that there are some identical integers, the 0 value inside the arr[]
         * must equal to the previous value. so we let 0 value to be the previous value;
         */
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] != 0 && arr[i + 1] == 0) {
                arr[i + 1] = arr[i];
            }
        }
        return arr;
    }
}

• 二维数组

public class project1_RankSort {
    public static void main(String[] args) {    
        int[][] testB = { { 71, 2 }, { 64, 8 }, { 31, 56 }, { 98, 1 }, { 3, 6 }, { 59, 837 }, { 49, 58 }, { 61, 8 } };
                
        // print the initial two-dimentional array;
        System.out.println("The initial two-dimensional array is:");
        for (int i = 0; i < testB.length; i++) {
            for (int j = 0; j < testB[0].length; j++) {
                System.out.print(testB[i][j] + " ");
            }
            System.out.println();
        }

        testB = RankSortArray(testB);

        System.out.println("The sorted two-dimensional array is:");
        // print the finished two-dimentional array;
        for (int i = 0; i < testB.length; i++) {
            for (int j = 0; j < testB[0].length; j++) {
                System.out.print(testB[i][j] + " ");
            }
            System.out.println();
        }

    }
    
    public static int[][] RankSortArray(int[][] a) {
        int[][] arr = new int[a.length][a[0].length]; // Defined a new array to be the sorted array;
        for (int i = 0; i < a.length; i++) {
            int index = 0; // Defined an index variable which is the first index of the integer in new
                           // array;

            /*
             * Find how many integers smaller than a[i], the number of them is the first
             * index of a[i][] in new array;
             */
            for (int j = 0; j < a.length; j++) {
                if (a[i][0] > a[j][0]) {
                    index++;
                }
            }

            for (int k = 0; k < 2; k++) {
                arr[index][k] = a[i][k];
            }
        }

        /*
         * To avoid there are many value of the same first value. we use a kind of
         * trick. The main mind of that is: 1. if there is a 2-d array whose first value
         * is 0(from the second value of arr[][]), arr[i][0] must equal to the
         * arr[i-1][0]; 2. we traversing the a[][], find the a[][0] == arr[i][0] and let
         * arr[i][1] = a[][1]; 3. we create a new variable number to account how many
         * times a[][0] == arr[i][0];
         */
        int number = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i][0] == 0) {
                arr[i][0] = arr[i - 1][0];
                if (number != 0) {
                    number = 1 - i;
                }
                for (int j = a.length - 1; j >= 0; j--) {
                    if (arr[i][0] == a[j][0]) {
                        number++;
                        if (number > 1) {
                            arr[i][1] = a[j][1];
                            break;
                        }
                    }
                }

            }
        }

        return arr;
    }
}

本文地址：https://blog.csdn.net/weixin_46698972/article/details/109253005