java插入排序遞歸

我有一個數組，並且必須使用插入排序對它們進行排序。我試圖使用compareTo方法來遍歷數組，看看更大。我遇到了一個問題，因爲我試圖引用一個顯然沒有工作的字符串的數組索引（compareTo（a [key]））。java插入排序遞歸

任何建議或提示如何做到這一點，將不勝感激。

這是我到目前爲止。這是一個好的開始？還是從正確的方向開始？

public void insertionSort() 
    { 
     insertionSort(a.length-1); 
    } 



    private void insertionSort(int n) 
    { 
     String temp; 
     if(n <= 1) 
     { 
     //Do nothing, easiest case 
     } 

     else 
     { 
     for(int i = 1; i < a.length; i++) 
     { 
     int j; 
     String key = a[i]; 

      while((j >= 0) && (a[i].compareTo(a[key]) > 0)) 
      { 
      a[i+1] = a[i]; 
      j--; 
      } 
      a[i+1] = key; 
     } 

     insertionSort(n-1); 

     } 
    }

來源

2011-09-28 alexthefourth

「我有陣列的串」 - 你的意思是「字符串數組」，對不對？ –

那是正確的，我改變了它 – alexthefourth

j應該在某處之前初始化while循環 – smas

如下更換內環：

j = i - 1; //initialize j!!! 
String key = a[i]; //take value 
while((j >= 0) && (a[j].compareTo(key) > 0)){//Compare with key!!! 
    a[j+1] = a[j]; 
    j--; 
} 
a[j + 1] = key; //index is j here!!!!

來源

2011-09-28 16:09:43 Cratylus

遇到一個數組越界越界異常在[i + 1] =鍵 – alexthefourth

它應該是'a [j + 1] = key'。同時刪除遞歸。即刪除'insertionSort（n-1）;' – Cratylus

它只是改變a[j].compareTo(key)（注意，要比較a[j]，不a[i]）。 smas評論說，你還需要初始化j。

來源

2011-09-28 16:04:38

我的第一個建議是，如果您傳遞所需的參數，通常會更容易理解方法。目前還不清楚a是什麼;我希望公衆insertionSort方法作爲一個參數的對象進行排序。（我想，如果你在自己的類列表上定義了這個類，它並沒有那麼糟糕，但聽起來不像是這種用法）。

同樣，我不完全確定n應該是什麼（大概是你知道排序後的索引），但你完全不用它在私有方法的主體中，所以你只是做同樣的事情n次。

您似乎也正在交換a的元素，在插入排序中您不需要這樣做。這看起來更像泡泡分類。

嘗試首先編寫方法作爲僞代碼（例如註釋）來佈局您的方法，然後用一小段代碼充實每個註釋。這樣做可以避免在細節上陷得太深，通常概念錯誤會更明顯，並且更容易避免。這可能看起來像：

public static int[] insertionSort(int[] input) { 
    // Create the array to hold the results 

    // Iterate through the contents of input and insert each one into 
    // the result array in order (method call here) 

    // return the result array 
} 

private void insertOneElement(int toInsert, int[] resultArray) { 
    // Compare toInsert with first element of resultArray 

    // etc. 
}

來源

2011-09-28 16:06:48

java插入排序遞歸

回答

相關問題