-1

我试图理解递归以及如何将我当前的迭代插入排序转换为递归排序。

我需要对我的代码做些什么才能使其递归？

  • 我想我需要一个基本案例，这样它就不会变成无限循环。
  • 我不确定我是否完全理解递归。也许你可以让我更清楚？
  • 我读了很多书，但我仍然不知道从哪里开始。

这是我的代码：

public class InsertionSort
{

    public static void main(String a[])
    {

        int i;
        int array[] =
        { 8, 33, 12, 99, 0, 17 };

        System.out.println("Values of Array before the sort: ");

        for (i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + "  ");
        }

        insertion_srt(array, array.length);

        System.out.println("");
        System.out.println("Values of Array after the sort: ");

        for (i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + "  ");
        }

    }

    public static void insertion_srt(int array[], int n)
    {

        for (int i = 1; i < n; i++)
        {

            int j = i;
            int B = array[i];

            while ((j > 0) && (array[j - 1] > B))
            {
                array[j] = array[j - 1];
                j--;
            }

            array[j] = B;
        }
    }
}
4

4 回答 4

1

这是我个人喜欢的好方法。它确实使用了三种方法，但它们很容易理解。将 insertOut 视为外部 for 循环，将 insertIn 视为内部嵌套 for 循环

public static void insertionRecursive(int[] a){
    if(a.length > 0){ // base case
        insertionOut(a, 1, a.length);
    }
}   
private static void insertionOut(int[] a, int i, int length){ //outer loop
    if(i < length){ // iterates from 1 to the length
        int temp = a[i]; // temp value
        int k = i;
        insertionIn(a, k, temp);
        insertionOut(a, i + 1, length); // iterates through the loop
    }
}
private static void insertionIn(int[] a, int k, int temp){ // inner loop
    if(k > 0 && a[k - 1] > temp){
       //this does a basic swap
        a[k] = temp;
        a[k] = a[k - 1];
        a[k - 1] = temp;
        insertionIn(a, k - 1, temp);    // iterates through the loop
    }
}
于 2014-12-10T10:24:35.493 回答
0

理解递归如何工作的一个好方法是理解分治算法的概念。这种技术是解决各种问题的有效算法的基础。

它背后的想法是将一个问题分成更小的子问题，这些子问题都可以用相同的方式解决：

  • 分成 2 个（或更多）子问题。
  • 递归解决每个子问题。
  • 结合结果。

插入排序不是分治算法的最佳示例，但仍然可以通过这种方式进行处理。您可以将问题分为 2 个子问题：

  • 最后一个元素
  • 其他一切

这样，您将获得所谓的尾递归。所有循环都相对容易转换为尾递归。

public static void insertion_srt(int array[], int n, int j) {
    if (j < n) {
        int i;
        int temp = array[j];

        for (i=j; i > 0 && array[i-1] > temp; i--) array[i] = array[i-1];
        array[i] = temp;

        insertion_srt(array,n, j+1);
    }
}
于 2012-10-03T09:44:18.513 回答
0

转换外部 for 循环是微不足道的。要克服 while 循环，您需要一些递归辅助函数。您必须在 main 中调用该函数insertion_srt(array, 0, array.length)：

public static void insertion_srt(int array[], int beg_index, int n) {
    if(beg_index >= n-1)
            return;
    int i = beg_index + 1;
    int j = i;
    int B = array[i];
    j=helper(array, j, B);
    array[j] = B;
    insertion_srt(array, beg_index + 1, n);
}

private static int helper(int[] array, int j, int B) {
    if(j <= 0 || array[j-1] <= B)
        return j;
    array[j] = array[j - 1];
    return helper(array, j-1, B);
}
于 2012-10-03T09:58:20.260 回答
-1

试试这个简单的递归方法：

public static void insertionSort(int[] array, int index) {
    if(array.length == index + 1) return;

    insertionSort(array, index + 1);

    // insert array[index] into the array

}
于 2012-10-03T09:49:25.880 回答