无法递归地将插入排序转换为

Question

public static void insertionSort(int[] a) {
for(int i = 1; i < a.length; i++) {
int minVal = a[i];
int checkIdx = i-1;

while(checkIdx >= 0 && minVal < a[checkIdx]) {
a[checkIdx + 1] = a[checkIdx];
checkIdx--;
}

a[checkIdx + 1] = minVal;
}
}

这是我迭代插入排序的解决方案，但我想要的是递归地转换此代码。我试过了，但有一部分卡住了。

public static void insertionSort(int[] arr, int i, int n)
{
int value = arr[i];
int j = i;
// Find index j within the sorted subset arr[0..i-1]
// where element arr[i] belongs
while (j > 0 && arr[j - 1] > value)
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = value;
// Note that subarray arr[j..i-1] is shifted to
// the right by one position i.e. arr[j+1..i]
if (i + 1 <= n) {
insertionSort(arr, i + 1, n);
}
}

我陷入了while循环部分，如何将其递归转换为？？

Answer 1

您就快到了。只有一件事。您需要在某个时刻突破递归。当数组被排序并且i+1==n时，这将是条件。经过轻微编辑的代码。原始数组为{4,2,7,8,1,9,3,5,6,0}，最终进行排序。

public class insertionSort_Edited {
public static int[] insertionSort (int[] arr, int i, int n){
int value = arr[i];
int j = i;
// Find index j within the sorted subset arr[0..i-1]
// where element arr[i] belongs
while (j > 0 && arr[j - 1] > value)
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = value;
// Note that subarray arr[j..i-1] is shifted to
// the right by one position i.e. arr[j+1..i]
if (i + 1 < n ) {
insertionSort(arr, i + 1, n);
}
return arr;
}
public static void main(String[] args) {
int[] MyArray= new int[]{4,2,7,8,1,9,3,5,6,0};
MyArray = insertionSort(MyArray, 0, 10);
for(int i=0;i<MyArray.length;i++){
System.out.println(MyArray[i]);
}
}
}

给出以下输出。

0
1
2
3
4
5
6
7
8
9

Answer 2

好的，我已经解决了，谢谢你的帮助。

public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void check(int[] array, int i) {
if (i == 0) {
return;
} 
if (array[i] >= array[i - 1]) {
return;
} 
swap(array, i, i - 1);
check(array, i - 1);
}
public static void recurInsertionSort(int[] a, int minPos, int last) {
check(a,minPos);

if(minPos + 1 <= last) {
recurInsertionSort(a,minPos + 1, last);
}

}