Swap整數算法

我正在學習算法，並嘗試使用Swift交換到數組中的整數，我知道使用'swap'函數是有效的，但我嘗試學習不同的方法。所以我嘗試不同的方法，我不明白一兩件事 - 我有200個整數數組，當我用這個方法：Swap整數算法

func selectionSort(var array: [Int]) { 
print("Selection Sort") 
for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
      let temp = array[j] //runs 7282 times 
      array[j] = array[i] // runs 7282 times 
      array[i] = temp  // runs 7282 times 
     } 
    } 
} 
print(array) 
}

運行7秒，並交換代碼運行7282（左右）次，但是當我使用這個：

func selectionSort(var array: [Int]) { 
    print("Selection Sort") 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
      array.insert(array[j], atIndex: i) 
      array.removeAtIndex(j+1) 

     } 
    } 
    } 
    print(array) 
}

它只能運行198次1.3秒了嗎？

我不明白爲什麼運行次數會有這樣的不同？它只出現在選擇排序中。如果我使用氣泡排序，則運行次數沒有這種差異。

來源

2016-06-08 Евгений Митько

你在兩個例子中獲得排序數組嗎？它看起來像第二種方法刪除其中一個值，並重復其他值，這意味着您的實現可能不正確。你會希望執行所提到的代碼的次數更少，因爲如果你複製數組中的每個值，它周圍的謂詞不會更經常。 – Glubus

經過進一步審查，我想我找到了問題。第一類將不得不多次移動該數字才能將其置於正確的位置。第二類同時移動多個號碼，因爲插入將推送數組中的其他號碼。我用5個整數數組對它進行了測試。

這裏是調試器中的第一個排序方法開始之前：

注意如何3遠離其正確位置，現在第一種方法排序一次後，數組現在看起來是這樣

現在3處於正確的位置，但是4現在距離它的正確位置很遠。它將不得不重複這個動作4次，直到它到達最終位置。接下來的交換看起來像這樣

現在14在17，因爲它應該前移動，但其仍遠離其正確位置。所以它將不得不再次移動！

讓我們看看第二種排序方法。

這裏是什麼樣子的排序之前

和第一個交換後，它看起來像這樣

現在你可以看到只有一個交換後，3 AND 4處於正確的位置。 3只移動了一次，正因爲如此，它被移動到了4的前面，將4移到了正確的位置。

現在又一次交換...現在

你可以看到，它已經經過使用第二種方法2個互換正確排序，但它採取了第一種方法4個互換。只有當你有一個更大的陣列時，差異才會增長。

第二種方法通過每次插入一個時間索引推回數字移動多個號碼...

一個例子：4,17,14,3,20

4是目前在索引0
17目前是在索引1目前
14是在索引2

如果我在第3插入E前...

3,4,17,14,3,20

現在刪除以前的3 ...

3,4,17,14,20

4現在在索引1！
17現在在索引2！
14現在在索引3！

來源

2016-06-08 13:32:08

他正在使用一個插入並刪除每次，這保持陣列數相同 – Scriptable

@Scriptable你是對的。我錯了，我編輯了我的答案。我認爲我發現問題 –

良好的調查，代碼讀取像它的完全相同的功能，但它不是。對我來說，它仍然沒有多大意義，它是如何移動多個數字：（ – Scriptable

方法有很大不同。

第一個按照您的預期每次都會進行簡單的交換array[j] < array[i]。

第二個，當array[j] < array[i]是真實的，它移動array[j]到i個位置和由一個位置移動所述陣列的其餘部分。

話雖這麼說，我有一點時間在我的手上，所以我決定寫在斯威夫特3的算法（請注意，您如何避免使用temp）：

func selectionSort(_ array: [Int]) { 
    var array = array 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
     (array[j], array[i]) = (array[i], array[j]) 
     } 
    } 
    } 
    print(array) 
} 

func selectionSort2(_ array: [Int]) { 
    var array = array 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
     array.insert(array[j], at: i) 
     array.remove(at: j+1) 
     } 
    } 
    } 
    print(array) 
}

乾杯！

來源

2016-07-01 11:01:54

回答

相關問題