需要幫助理解插入排序

Question

在這段代碼是如何工作的（JAVA）：

/** Move A[A.length-1] to the first position, k, in A such that there 
* are no smaller elements after it, moving all elements 
* A[k .. A.length-2] over to A[k+1 .. A.length-1]. */ 

static void moveOver (int A[]) { 
    moveOver (A, A.length-1); 
} 

/** Move A[U] to the first position, k<=U, in A such that there 
* are no smaller elements after it, moving all elements 
* A[k .. U-1] over to A[k+1 .. U]. */ 

static void moveOver (int A[], int U) { 
    if (U > 0) { 
    if (A[U-1] > A[U]) { 
     /* Swap A[U], A[U-1] */ 
    moveOver (A, U-1); 
    } 
    } 
} 

我從伯克利CS類，我會通過網上，自學了這一點。這不是作業（我希望是但不是那幸運）。我不明白的是：

假設A []中的數字是8,2,10,5,4,12。當我在上面使用它們時，我在我的迭代中得到這個，追蹤它。

1. 上最下標是U，或在 這種情況下如圖12所示，U-1是4，沒有交換是 完成
現在
2. U是4（遞歸U-1）和上面的數字是5（另一個U-1）。他們互換。
3. U現在是4，因爲四個只是向上移動而10個是U-1他們交換。

我的順序現在是8,2,4,10,5,12。

我的問題是如何獲得我已經通過的數字？例如，如果我從不回到那個下標來測試，我將如何得到五個，例如，向上移動。

我不認爲我正在跟蹤程序，我被混淆與遞歸。爲了這個原因，請假定交換正確完成。

謝謝。

SE

Answer 1

至於你跟蹤：你在第2點是走錯了，因爲if條件不成立，所以沒有遞歸調用做過。

如果遞歸混淆你，它可能有助於改寫成一個迭代形式：

static void moveOver (int A[], int U) { 
    while (U > 0 && A[U-1] > A[U]) { 
    /* Swap A[U], A[U-1] */ 
    --U; 
    } 
} 

現在很容易地看到，環路將盡快遇到一個更小的元素停止。爲了成爲一個完整的排序算法，需要做更多的工作。無論哪種方式，這不是插入排序;它看起來更像是我的一部分泡泡。

現在你說你從哪裏得到這段代碼？

Answer 2

我認爲關鍵的問題你的錯誤理解，實際上是隱藏在你的問題

需要幫助理解插入的標題排序

算法確實只排序當前元素，但其想法是每次將元素添加到數組時它都會運行。這種方式每次被稱爲數組的其餘部分已經是有序的。換句話說，你只是試圖分解最後一個元素的位置。

因此，使用您的示例數字（8,2,10,5,4,12）並按順序將它們按順序添加/排序到數組中，順序如下（每個步驟的排序都會發生你究竟如何描述）：

To be added   | old array  | after push  | Result (after moveOver()) 
(8, 2, 10, 5, 4, 12)| []    | [8]   | [8] 
(2, 10, 5, 4, 12) | [8]   | [8,2]   | [2,8] 
(10, 5, 4, 12)  | [2,8]   | [2,8,10]  | [2,8,10] 
(5, 4, 12)   | [2,8,10]  | [2,8,10,5]  | [2,5,8,10] 
(4, 12)    | [2,5,8,10]  | [2,5,8,10,4] | [2,4,5,8,10] 
(12)    | [2,4,5,8,10] | [2,4,5,8,10,12]| [2,4,5,8,10,12]