为什么选择排序不贪心

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不是，但很难称为实用）。此外，将这些排序算法作为贪婪优化问题来配制，这样在比较排序算法时会在实践中模糊实际上非常重要的细节。

因此，我认为将特征选择排序或任何其他排序算法视为贪婪在技术上是有效的，但实际上是无用的，因为这样的分类不提供真正有用的信息。