代码之家  ›  专栏  ›  技术社区  ›  rohan510

Java中使用递归算法的插入排序(无循环)

  •  -4
  • rohan510  · 技术社区  · 7 年前

    我试图使用递归算法进行插入排序,但它不能包含任何类型的迭代循环。 这是我写的代码;它似乎不起作用

    class Sort {
        public int shift(int[] a, int j, int k){
            if(j>=0 && k< a[j]){
                a[j + 1] = a[j];
                j--;
                shift(a,j, k);
            }
            return j;
        }
    
        public void IS(int a[], int i){
            int j, temp;
            if(i<a.length){
                j = i-1;
                temp = a[i];
                a[shift(a,j,temp)+1]=temp;
                IS(a,i+1);
            }
        }    
    }
    

    这个 i in IS()从1开始。 我对我的shift()方法感到困惑。如果使用下面的代码,则它可以工作。我试图将while循环转化为递归算法,但我总是得到错误的输出。

    while (j >= 0 && temp<data[j]) {
      a[j + 1] = a[j];
      j--;
    }
    
    1 回复  |  直到 7 年前
        1
  •  0
  •   Stefan    7 年前

    我假设您开始递归(例如):

        int[] values = new int[] {7, 9, 1, 8, 2};
        IS(values, 0);
    

    如果打印输出,您会看到您的解决方案正在达到解决方案,但还没有达到。本例的输出: 7, 1, 8, 2, 9 . 实际上,唯一发生的事情是 9 已经右转了几次。

    需要更多的转换。你可以打电话 IS

    public void metaIS(int[] a, int i) {
        IS(a, 0);
        if (i < a.length) {
            metaIS(a, i + 1);
        }
    }
    

    也就是说,如果数组长度为5个数字,则调用次数为5次,并且一切正常: 1, 2, 7, 8, 9

    顺便说一句,重命名该方法可能是个好主意。当人们听到 ,递归问题解决并不是他们想到的第一件事。一种常见的约定是方法名以非大写字母开头。