为什么选择排序不贪心
Why selection sort is not greedy
我发现选择排序使用蛮力策略。但是，我认为它使用了贪心策略。
为什么我认为它使用Greedy：它在外循环从0到n-1，从i+1到n-1。这实在是太天真了。它在每次迭代中选择一个中的最小元素 - 它在本地选择最佳元素。一切都像 Greedy 中的一样，但事实并非如此。
你能解释一下为什么不是我想的那样吗？关于这个问题的信息我还没有在网上找到。
设 A 为整数列表，使得：A = [5, 4, 3, 6, 1, 2, 7 ]
贪心算法会寻找最有希望的方向，因此：
- 我们将比较：5和4，看到4确实小于5，将4设为我们的最小值
- 将 4 与 3 进行比较，将 3 设置为我们的最小值
- 现在我们将 3 与 6 进行比较，这是棘手的部分：在正常的选择排序（强力）中，我们将继续考虑剩余的数字，在贪婪的方法中，我们将取 3 作为最小值，而不会考虑剩余的数字，因此 "Best locally".
所以使用这种方法的排序列表将导致这样排序的列表：
[3、4、5、1、2、7]
贪婪和蛮力描述了算法的不同特征。
Greedy 意味着每一步的算法都会选择一些 locally 最好的选项。也就是说，它没有前瞻性。
Brute-force 意味着算法以直接的方式寻找选项，考虑所有选项。例如。它可能会通过二进制搜索来搜索一个元素，并且它不会再是蛮力了。
所以这个算法可能是贪婪的和暴力的。这些品质并不相互排斥。
选择排序确实可以描述为贪心算法，因为它：
- 尝试选择一个输出（其输入的排列）来优化某个度量（"sortedness"，可以通过多种方式来衡量，例如通过 inversions 的数量），并且
- 通过将任务分解为更小的子问题（对于选择排序，在输出排列中找到第 k 个元素）并为每个子问题选择局部最优解来做到这一点。
碰巧，相同的描述也适用于大多数其他排序算法——唯一真正的区别是子问题的选择。例如：
- 插入排序局部优化 k 个第一个输入元素的排列排序；
- 冒泡排序优化相邻元素对的排序；它需要多次迭代列表才能达到全局最优，但这仍然属于贪婪算法的广义定义；
- 合并排序优化输入序列的指数增长子序列的排序；
- quicksort 递归地将其输入划分为任意选择的主元两侧的子序列，优化划分以最大化每个阶段的排序。
的确，在我的脑海中，我想不出任何在这个意义上不会贪婪的实用排序算法。 （Bogosort 不是，但很难称之为实用。）此外，将这些排序算法表述为像这样的贪心优化问题相当模糊了在比较排序算法时实际重要的细节。
因此，我认为将选择排序或任何其他排序算法描述为贪婪在技术上是有效的，但实际上是无用的，因为这种分类没有提供真正有用的信息。
我发现选择排序使用蛮力策略。但是，我认为它使用了贪心策略。
为什么我认为它使用Greedy：它在外循环从0到n-1，从i+1到n-1。这实在是太天真了。它在每次迭代中选择一个中的最小元素 - 它在本地选择最佳元素。一切都像 Greedy 中的一样，但事实并非如此。
你能解释一下为什么不是我想的那样吗？关于这个问题的信息我还没有在网上找到。
设 A 为整数列表，使得：A = [5, 4, 3, 6, 1, 2, 7 ]
贪心算法会寻找最有希望的方向，因此：
- 我们将比较：5和4，看到4确实小于5，将4设为我们的最小值
- 将 4 与 3 进行比较，将 3 设置为我们的最小值
- 现在我们将 3 与 6 进行比较，这是棘手的部分：在正常的选择排序（强力）中，我们将继续考虑剩余的数字，在贪婪的方法中，我们将取 3 作为最小值，而不会考虑剩余的数字，因此 "Best locally".
所以使用这种方法的排序列表将导致这样排序的列表： [3、4、5、1、2、7]
贪婪和蛮力描述了算法的不同特征。
Greedy 意味着每一步的算法都会选择一些 locally 最好的选项。也就是说，它没有前瞻性。
Brute-force 意味着算法以直接的方式寻找选项，考虑所有选项。例如。它可能会通过二进制搜索来搜索一个元素，并且它不会再是蛮力了。
所以这个算法可能是贪婪的和暴力的。这些品质并不相互排斥。
选择排序确实可以描述为贪心算法，因为它：
- 尝试选择一个输出（其输入的排列）来优化某个度量（"sortedness"，可以通过多种方式来衡量，例如通过 inversions 的数量），并且
- 通过将任务分解为更小的子问题（对于选择排序，在输出排列中找到第 k 个元素）并为每个子问题选择局部最优解来做到这一点。
碰巧，相同的描述也适用于大多数其他排序算法——唯一真正的区别是子问题的选择。例如：
- 插入排序局部优化 k 个第一个输入元素的排列排序；
- 冒泡排序优化相邻元素对的排序；它需要多次迭代列表才能达到全局最优，但这仍然属于贪婪算法的广义定义；
- 合并排序优化输入序列的指数增长子序列的排序；
- quicksort 递归地将其输入划分为任意选择的主元两侧的子序列，优化划分以最大化每个阶段的排序。
的确，在我的脑海中，我想不出任何在这个意义上不会贪婪的实用排序算法。 （Bogosort 不是，但很难称之为实用。）此外，将这些排序算法表述为像这样的贪心优化问题相当模糊了在比较排序算法时实际重要的细节。
因此，我认为将选择排序或任何其他排序算法描述为贪婪在技术上是有效的，但实际上是无用的，因为这种分类没有提供真正有用的信息。