Matlab - 排序算法
Matlab - Sorting algorithms
我一直在研究各种排序算法，例如 Matlab 中的合并、冒泡、快速和桶类型排序，并有几个问题。它指出插入排序、冒泡排序和快速排序的 运行 时间是 O(n^2)，而合并和分桶的 运行 时间是 O(nlog(n))。我想知道为什么，如果最后两个只是更快，那是使用前三个中的任何一个的原因。如果列表排序更多/排序更少，更大/更小等，它们是否更快，或者是否有其他原因？
插入排序用于已知非常小的数组，因为在这种情况下它通常是最快的。
快速排序在实践中被大量使用，因为它有 expected N log N 次，在大多数情况下速度相当快，并且在数组上就地工作——你不需要分配备份数组。
归并排序用于链表，有时当您确实需要 O(N log N) 时间或您确实需要稳定排序时用于数组。 （快速排序不稳定）。对数组使用合并排序需要您分配一个备用数组，您可以在合并期间将其用作临时存储。
桶排序只适用于某些类型的数据，所以并不常见，但是当数据适合时可以使用它，效果很好。它通常也被认为是 O(N)
当您不需要稳定排序并且确实需要 O(N log N) 时间时，堆排序可用于数组。它也不稳定，而且在大多数情况下比快速排序慢。
哦，至于冒泡排序……好吧，没有人使用冒泡排序
我不确定这将如何应用于 Matlab，因为我不知道它的排序算法是如何实现的。
除了在整数数组排序等情况下速度最快的基数排序外，快速排序与合并排序对接近随机数据的平均时间接近，但合并排序需要 O(n) space .归并排序稳定（保留相等元素的顺序），而快速排序不稳定
快速排序比归并排序进行更多的比较，但移动更少。哪个更快受此影响。如果使用用户定义的函数进行比较，合并排序通常会更快一些。
在具有 16 个寄存器的处理器上，例如 64 位模式的 PC，则 4 路归并排序将比快速排序或标准的 2 路归并排序快一点。 4 路合并排序进行 1.5 次比较，但移动 0.5 次，因此基本操作的总数是相同的，但比较往往对缓存更友好，因此 4 路更快一些。对于大型随机整数数组，这些排序方法之间的差异通常小于 10%，因此实际差异不大。
多核处理器上的多线程有很大的不同。我对 1600 万个伪随机 32 位整数的数组进行基准标记排序，四线程（自下而上/迭代）合并排序的速度大约是单线程（自下而上/迭代）合并排序的 3 倍（0.5 秒对 1.5 秒）秒）。主要好处是在每个核心的本地缓存中发生了多少排序。
我一直在研究各种排序算法，例如 Matlab 中的合并、冒泡、快速和桶类型排序，并有几个问题。它指出插入排序、冒泡排序和快速排序的 运行 时间是 O(n^2)，而合并和分桶的 运行 时间是 O(nlog(n))。我想知道为什么，如果最后两个只是更快，那是使用前三个中的任何一个的原因。如果列表排序更多/排序更少，更大/更小等，它们是否更快，或者是否有其他原因？
插入排序用于已知非常小的数组，因为在这种情况下它通常是最快的。
快速排序在实践中被大量使用，因为它有 expected N log N 次，在大多数情况下速度相当快，并且在数组上就地工作——你不需要分配备份数组。
归并排序用于链表，有时当您确实需要 O(N log N) 时间或您确实需要稳定排序时用于数组。 （快速排序不稳定）。对数组使用合并排序需要您分配一个备用数组，您可以在合并期间将其用作临时存储。
桶排序只适用于某些类型的数据，所以并不常见，但是当数据适合时可以使用它，效果很好。它通常也被认为是 O(N)
当您不需要稳定排序并且确实需要 O(N log N) 时间时，堆排序可用于数组。它也不稳定，而且在大多数情况下比快速排序慢。
哦，至于冒泡排序……好吧，没有人使用冒泡排序
我不确定这将如何应用于 Matlab，因为我不知道它的排序算法是如何实现的。
除了在整数数组排序等情况下速度最快的基数排序外，快速排序与合并排序对接近随机数据的平均时间接近，但合并排序需要 O(n) space .归并排序稳定（保留相等元素的顺序），而快速排序不稳定
快速排序比归并排序进行更多的比较，但移动更少。哪个更快受此影响。如果使用用户定义的函数进行比较，合并排序通常会更快一些。
在具有 16 个寄存器的处理器上，例如 64 位模式的 PC，则 4 路归并排序将比快速排序或标准的 2 路归并排序快一点。 4 路合并排序进行 1.5 次比较，但移动 0.5 次，因此基本操作的总数是相同的，但比较往往对缓存更友好，因此 4 路更快一些。对于大型随机整数数组，这些排序方法之间的差异通常小于 10%，因此实际差异不大。
多核处理器上的多线程有很大的不同。我对 1600 万个伪随机 32 位整数的数组进行基准标记排序，四线程（自下而上/迭代）合并排序的速度大约是单线程（自下而上/迭代）合并排序的 3 倍（0.5 秒对 1.5 秒）秒）。主要好处是在每个核心的本地缓存中发生了多少排序。