所以在讲座中我们已经讨论了选择、插入、冒泡、合并、快速、堆和基数排序。所以现在我应该在以下情况下决定最好的算法,并描述我为什么选择那个算法。
1) 对一组可比较的元素进行排序 :我会说堆/合并排序,因为它们在所有情况下都具有 O(n logn) 时间复杂度。还是快速排序?
2) 对一组 32 位数字的元素进行排序 : 也许基数排序,但我不确定。
3) 在排列成本高且比较不是 的条件下对一组可比较元素进行排序:我的猜测是选择排序,因为您确实有很多比较,但只有 (n-1) 个 Action 。
4) 在您知道前 (n-m) 个元素已排序且只有最后 m 个元素未排序的条件下,对一组可比较的元素进行排序。是否存在 O(m log n) 或 O(n log m) 过程? : 因为这个 https://www.toptal.com/developers/sorting-algorithms/ 我会说插入排序,但我对问题的其余部分一无所知。
5) 在 future 少于 n^2 次操作的特定期限内需要解决方案的条件下对一组可比元素进行排序 : 因为快速排序的最坏情况是n^2,所以我会选择合并或堆排序。
6) 对一组可比较的元素进行排序,但过程应该是稳定的 :这必须是归并排序,因为所有其他算法都不稳定。
最佳答案
好吧,有几个错误的问题。
第一个:对一组可比较的对象进行排序:如果我没有错,那么每个对象都是可比较的。 Offcourse 字符串可以在没有comapring 的情况下进行排序,但这是一种特殊情况。
我将选择带有随机随机播放的快速排序以避免最坏的情况。尝试在 Mergesort 和 QuickSort 上加倍比率测试,您会注意到随着大小的增加,mergesort 会变得更慢。但是,可以通过在递归调用中使用插入排序来改进合并排序。
2:这与排序字符串相同,它完全取决于您要如何对它们进行排序?根据第一位,最后一位或全部应该排序?所以他们有很多算法:默沙东 , 迷幻药 , Quick-3wayString 排序 .
4: 在您知道前 (n-m) 个元素已排序且只有最后 m 个元素未排序的条件下,对一组可比较的元素进行排序。是否存在 O(m log n) 或 O(n log m) 进程:你能在合并排序的基本情况下使用插入排序吗所以它总是将数组分成两半 (n-m) 和 (m+1 - n)?因为插入排序会在只制作 之后打破它的循环。 n 比较,另一半将通过 中的 mergesort 进行排序NlogN 你得到上限为 NlogN .
5:在 future 小于n^2次操作的特定期限内需要解决方案的条件下对一组可比元素进行排序:我也会选择合并排序,但如果允许我改变算法,那么我将使用带有随机随机播放的快速排序,(注意:你仍然有机会获得 n^2 时间复杂度)。
6:是的,如果您必须从这些算法中进行选择,那么 Mergesort 是唯一的一种。
关于algorithm - 在以下这些情况下,哪种排序算法最好?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50274020/