algorithm - Matlab - 排序算法

Question

我一直在研究各种排序算法，例如 Matlab 中的合并、冒泡、快速和桶型排序，并有几个问题。它指出插入排序、冒泡排序和快速排序的运行时间是 O(n^2)，而合并和分桶的运行时间是 O(nlog(n))。我想知道为什么，如果最后两个只是更快，那是使用前三个中任何一个的原因。如果列表排序更多/排序更少，更大/更小等，它们是否更快，或者是否有其他原因？

Answer 1

插入排序用于已知非常小的数组，因为在这种情况下它通常是最快的。

快速排序在实践中被大量使用，因为它预期 N log N 次，在大多数情况下速度相当快，并且可以在数组上就地工作——您不需要分配一个备份数组。

归并排序用于链表，有时当您确实需要 O(N log N) 时间或您确实需要稳定排序时用于数组。 (快速排序不稳定)。对数组使用合并排序需要您分配一个备用数组，您可以在合并期间将其用作临时存储。

桶排序只适用于某些类型的数据，所以并不常见，但是当数据适合时，你可以用它来达到很好的效果。它通常也被认为是 O(N)

当您不需要稳定排序并且您确实需要 O(N log N) 时间时，可在数组上使用堆排序。它也不稳定，并且在大多数情况下比快速排序慢。

哦，至于冒泡排序......好吧，没有人使用冒泡排序