爲什麼選擇排序不貪心

Question

我發現選擇排序使用蠻力策略。不過，我認爲它使用貪婪策略。

爲什麼我認爲它使用貪婪：它在外循環和從i + 1到n-1從0到n-1。這真的很天真。它在每次迭代中選擇最小元素 - 它在本地選擇最佳元素。一切都喜歡貪婪，但事實並非如此。

你能解釋一下爲什麼我不這麼認爲嗎？關於這個問題的信息我還沒有在互聯網上找到。

Answer 1

設A是intgers的列表，使得：A = [5,4，3，6，1，2，7]

貪婪算法將尋找最有前途的方向，因此：

1. 我們將比較：5比4，看到4確實是小於5，設置4作爲我們的最低
2. 比較4比3，設置3作爲我們的最低
3. 現在我們比較3-6，在這裏是一個棘手的部分：雖然在正常的選擇排序（蠻力），我們將繼續考慮剩下的數字，在a中貪婪的方法，我們將3作爲最低限度，不會考慮剩餘的數字，因此「本地最佳」。

所以使用這種方法的排序列表將導致排序作爲這樣的列表： [3，4，5，1，2，7]

Answer 2

貪婪和蠻力描述算法的不同性狀。

貪婪意味着，在每個步驟中的算法選擇一些選項，這是局部最好的。也就是說，它沒有前瞻性。

蠻力意味着該算法以一種簡單的方式查找選項，並考慮它們。例如。它可能會通過二進制搜索來搜索一個元素，並且它不再是蠻力。

所以算法可能既貪婪又蠻力。這些品質不是相互排斥的。

Answer 3

甲選擇排序確實可以被描述爲一個貪婪算法，在某種意義上說，它：

• 嘗試選擇優化某一度量（「有序性」的輸出（其輸入的置換），其可以以各種方式進行測量，例如通過編號inversions），並且
• 通過將任務分成更小的子問題（用於選擇排序，在輸出排列中找到第 - 個元素）並且選擇本地每個子問題的最優解。

碰巧，同樣的描述可以應用於大多數其他排序算法，以及—唯一真正的區別是子問題的選擇。例如：

• 插入排序局部優化的ķ第一輸入元件的排列的有序性;
• 氣泡排序優化相鄰元素對的排序;它需要多次遍歷列表以達到全局最優，但這仍然屬於貪婪算法的廣泛定義;
• 合併排序優化了輸入序列的指數增長子序列的排序;
• 快速排序遞歸地將其輸入劃分爲任意選擇的關鍵點任意一側的子序列，優化劃分以最大化每個階段的排序。

事實上，從我的頭頂，我想不出任何實際的排序算法，不會在這個意義上貪婪的。 （Bogosort不是，但很難稱爲實用）。此外，將這些排序算法作爲貪婪優化問題來配製，這樣在比較排序算法時會在實踐中模糊實際上非常重要的細節。

因此，我認爲將特徵選擇排序或任何其他排序算法視爲貪婪在技術上是有效的，但實際上是無用的，因爲這樣的分類不提供真正有用的信息。