为什么选择排序不贪婪

Question

我发现选择排序使用蛮力策略。但是，我认为它使用了贪婪策略。

为什么我认为它使用 Greedy：它在外循环从 0 到 n-1，从 i+1 到 n-1。这真是太天真了。它在每次迭代中选择一个中的最小元素——它在本地选择最好的。一切都像贪婪，但事实并非如此。

你能解释一下为什么这不是我的想法吗？我在 Internet 上没有找到有关此问题的信息。

Answer 1

选择排序确实可以被描述为一种贪心算法，因为它：

• 尝试选择一个输出（其输入的排列）来优化某个度量（“排序度”，可以用各种方式来度量，例如通过反转次数），以及
• 通过将任务分解为更小的子问题（对于选择排序，在输出排列中找到第k个元素）并为每个子问题选择局部最优解来实现。

碰巧的是，同样的描述也适用于大多数其他排序算法——唯一真正的区别是子问题的选择。例如：

• 插入排序局部优化k个第一个输入元素排列的排序性；
• 冒泡排序优化相邻元素对的排序；它需要多次迭代列表才能达到全局最优，但这仍然属于贪婪算法的广泛定义；
• 归并排序优化输入序列的指数增长子序列的排序性；
• 快速排序将其输入递归地划分为任意选择的主元两侧的子序列，优化划分以最大化每个阶段的排序度。

事实上，在我的脑海里，我想不出任何实用的排序算法在这个意义上不会贪婪。（Bogosort不是，但很难被称为实用。）此外，将这些排序算法表述为这样的贪婪优化问题相当模糊了在比较排序算法时在实践中实际重要的细节。

因此，我想说，将选择排序或任何其他排序算法的特征描述为贪婪在技术上是有效的，但实际上毫无用处，因为这种分类没有提供真正有用的信息。