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
上一篇: 算法之字符串匹配
推荐阅读
-
java插入排序 Insert sort实例
-
JAVA基于Arrays.sort()实现数组升序和降序
-
Java.lang.Arrays中的toString()和sort()基本使用形式
-
5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)
-
Java排序的那些事之sort方法的使用详解
-
java冒泡排序Bubble Sort算法代码
-
Java对学生成绩排序——通过list.sort()对list进行排序
-
Java中Arrays.sort()的三种常用用法(自定义排序规则)
-
Rank Sort in Java -Yuan.
-
浅谈Java中Collections.sort对List排序的两种方法