Java（ループなし）で再帰アルゴリズムを使用した挿入ソート

Question

再帰アルゴリズムを使用して挿入ソートをしようとしていますが、繰り返しループは一切使用できません。 ここに私が書いたコードです。 ISでi（）は1 から始まる

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); 
     } 
    }  
} 

私は私のシフト（）メソッドについて困惑している動作するようには思えません。以下のコードを使用している場合、それは動作します。 whileループを再帰的アルゴリズムに変えようとしていますが、私は常に間違った出力を得ています。

while (j >= 0 && temp<data[j]) { 
    a[j + 1] = a[j]; 
    j--; 
} 

Answer 1

私はあなたがこのようなあなたの再帰（例えば）を開始仮定：あなたは出力を印刷する場合

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

あなたはあなたのソリューションが解決策に到達していることがわかりますが、それはまだかなりありません。この例の出力は7, 1, 8, 2, 9です。効果的に、起こったのは9が数回右に移動したことだけです。

さらにシフトが必要です。 ISを何回か呼び出すことでそれを行うことができます。これは、パフォーマンスの観点からデッド醜いですが、それは動作します：

配列は、5つの数字の長さで5回あれば、通話がISであり、すべてが良いです

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

：ところで1, 2, 7, 8, 9

、メソッドの名前を変更することをお勧めします。人々がISを聞くとき、再帰的な問題解決は、彼らの心に来る最初のものではありません。一般的な方法は、メソッド名を非大文字で開始することです。