我发现选择排序使用暴力策略。不过，我认为它使用了贪婪策略。
为什么我认为它使用贪婪：它在外循环中从 0 到 n-1，从 i+1 到 n-1。这实在是太天真了。它在每次迭代中选择最小元素 - 它选择本地最好的元素。一切都像《贪婪》中的那样，但事实并非如此。
你能解释一下为什么这不是我想的那样吗？我在网上没有找到关于这个问题的信息。
选择排序确实可以被描述为贪婪算法，因为它：
- 尝试选择一个输出（其输入的排列）来优化某个度量（“排序”，可以通过多种方式来度量，例如通过数量倒转 https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)), and
- 通过将任务分解为更小的子问题来实现这一点（对于选择排序，找到k-输出排列中的第一个元素）并为每个子问题选择局部最优解。
事实上，相同的描述也可以应用于大多数其他排序算法——唯一真正的区别是子问题的选择。例如：
- 插入排序局部优化排列的排序性k第一个输入元素；
- 冒泡排序优化了相邻元素对的排序性；它需要多次迭代列表才能达到全局最优，但这仍然属于贪婪算法的广义定义；
- 归并排序优化了输入序列的指数增长子序列的排序性；
- 快速排序递归地将其输入划分为任意选择的主元两侧的子序列，优化划分以最大化每个阶段的排序性。
事实上，我想不出任何实用的排序算法wouldn't在这个意义上要贪婪。 (Bogosort https://en.wikipedia.org/wiki/Bogosort不是，但很难被称为实用。）此外，将这些排序算法表述为像这样的贪婪优化问题，会掩盖在比较排序算法时在实践中实际重要的细节。
因此，我想说，将选择排序或任何其他排序算法描述为贪婪在技术上是有效的，但实际上是无用的，因为这种分类没有提供真正有用的信息。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
