欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Rank Sort in Java -Yuan.

程序员文章站 2022-07-10 18:19:57
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, 5...

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