所以我有这个数组,我必须使用 Insertionssort 对其进行排序:
( 4 1 2 3 )= arr[0] ,
( 1 2 3 4 )=arr[1] ,
( 4 3 2 1 ) = arr[2],
( 3 1 2 4 )= arr[3] ,
( 4 3 1 2 ) = arr[4] ,
( 2 1 3 4 ) = arr[5] ,
( 4 1 3 2 ) = arr[6] ,
( 1 4 2 3 )= arr[7]
如果数组 1 的值 1 - 4 与数组 2 的值 1-4 之间的差值较大,则一个数组将与另一个数组交换。例如:arr[0] < arr[1],因为 1(4-3) < 3(4-1)。如果差异相同,则将比较值:例如:arr[5] 和 arr[6] 具有相同的差异(2),但 arr[6].value(1) > arr[5].value(1 ) --> 交换。
所以排序后的数组将如下所示:
(3,1,2,4) < (4,1,2,3) < (1,4,2,3) < (2,1,3,4) < (4,1,3,2) < (4,3,1,2) < (1,2,3,4) < (4,3,2,1)
我有这个方法 atm,只是检查第一个标准:
public int insertionsort(permutation[] arr, int gap) {
int count = 0;
for (int i = gap; i<arr.length-1; i++) {
count++;
permutation new = arr[i];
int k = i;
System.out.println("K: " + k);
System.out.println("gap: "+ gap);
while(Math.abs(arr[i].value(1)-arr[i].value(4)) > Math.abs(arr[i-gap].value(1) -
arr[i-gap].value(4))) {
arr[k] = arr[k-gap];
k = k-gap;
System.out.println("k-gap: " + (k-gap));
}
arr[k] = new;
}
return count;
}
现在我认为我的数组将首先按照小差异的顺序进行排序,但这似乎不正确。我希望你能帮助我!
最佳答案
我不清楚 gap
参数的目的是什么,希望您可以根据需要合并它,但这里是标准 Insertion Sort 到 Java 的直接翻译方法。
static void sort(permutation[] perms)
{
for(int i=1; i<perms.length; i++)
{
permutation fixed = perms[i];
int j = i - 1;
while(j >= 0 && perms[j].compareTo(fixed) > 0)
{
perms[j+1] = perms[j];
j -= 1;
}
perms[j+1] = fixed;
}
}
猜测一下排列
类可能是什么样子:
static class permutation
{
int len;
int[] arr;
public permutation(int... vals)
{
len = vals.length;
arr = vals.clone();
}
int value(int pos)
{
return arr[pos-1];
}
public int compareTo(permutation p)
{
int cmp = Math.abs(value(1)-value(len)) - Math.abs(p.value(1)-p.value(len));
if(cmp == 0)
for(int i=1; cmp==0 && i<=len; i++)
cmp = value(i)-p.value(i);
return cmp;
}
}
测试:
permutation[] perms = {
new permutation(4,1,2,3),
new permutation(1,2,3,4),
new permutation(4,3,2,1),
new permutation(3,1,2,4),
new permutation(4,3,1,2),
new permutation(2,1,3,4),
new permutation(4,1,3,2),
new permutation(1,4,3,2)
};
sort(perms);
for(permutation p : perms)
System.out.println(Arrays.toString(p.arr));
输出:
[1, 4, 3, 2]
[3, 1, 2, 4]
[4, 1, 2, 3]
[2, 1, 3, 4]
[4, 1, 3, 2]
[4, 3, 1, 2]
[1, 2, 3, 4]
[4, 3, 2, 1]
关于java - 带排列的数组的插入排序 (Java),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61794986/