带置换的数组的Insertionsort(Java)
所以我有一个数组,我必须用insertionsort进行排序:
( 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]。价值(1)>;arr[5]。价值(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)
我有一个methode 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;
}
现在我想我的数组应该先按照微小差异的顺序进行排序,但它似乎不正确。我希望你能帮助我
# 1 楼答案
我不清楚
gap
参数的目的是什么,希望您可以在需要时将其合并,但是这里有一个标准Insertion Sort方法到Java的直接翻译猜测一下
permutation
类可能是什么样子:测试:
输出: