合并排序与快速排序实现

Question

我必须测量快速排序和合并排序在随机数文件中排序整数所需的时间。

我在网上读到，对于大量的数据，合并排序应该比快速排序更快，但我的测量结果恰恰相反，合并排序所需的时间几乎是快速排序的两倍。

这些算法的实现是我的问题吗？

测量结果：

快速排序：

• 5 milion int - 715,194,000 ns
• 10 milion int - 1,383,187,400 ns
• 50 milion int - 6,819,586,800 ns
• 100 milion int - 14,159,986,000 ns

H 111150 milion int - 22,431,202,200 nsH 212f 213

合并排序：

• 5毫安int - 1,644,349,000 ns

• 10毫安int - 2,186,410,800 ns

• 50毫安int - 14,427,917,500 ns

• 100毫安int - 26,487,337,400 ns

• 150毫安int - 42,229,109,700 ns

//快速排序实现公共静态无效quickSort(int[] a，int start，int end){ if(end - start < 2){ int[] pivtIndex =分区( a，start，end)；quickSort(a，start，pivtIndex)；quickSort(a，pivtIndex + 1，end)；} public静态int分区(int[]a，int start，int end){ int枢轴= astart；int i= start；int j= end；时间(i< j){ while(i =枢轴)；if(i < j){ ai = aj；} while(i

Answer 1

我认为，即使数组的大小为150 * 10^6，但由于以下原因，快速排序肯定获得了优势：

假设JAVA中整数的大小为4字节，

((150* 10^6 *4字节)/ 1024字节)/ 1024兆字节)~ 572 MB

L3缓存的大小约为50 MB。

因此，(572-50)~ 522 MB内存必须注意主内存的使用(不包括L1和L2，因为它们的大小相对较低)。

现在，对于额外的522 MB，合并排序必须得到主内存的帮助。

因此，合并排序显然必须使用主内存，这是附件数组所需的。

访问主存是一项繁重的操作，由于其附件数组，和合并排序比快速排序更需要对主内存的访问。

Answer 2

在理想世界或真正的随机数字列表中，快速排序应该是最好的，然而，当数据表现不佳时，也会出现一些问题。

这看起来像原始文件的很好的实现。我假设您已经检查了整数的排序是否正确。

在选择第一个元素作为枢轴时，应该检查一些角情况下的O(N^2)。

• 已经排序了，因为您选择了第一个元素作为枢轴。
• 器官管1,2,3,2,1也会导致错误行为。
• 反向排序，如果以最后一个元素作为枢轴
• 少数单元，那么尝试一个只有0，1
• 几乎排序错误的数字的模式。H 210f 211

对于合并排序，您需要检查(start + end)是否会导致整数溢出。

在合并排序中，还可以通过对分配进行一些智能交换来进行优化，以便只需要分配一次。

当子数组的长度降到某个阈值以下时，这两种算法都可以使用插入排序进行优化，该阈值通常在11-32范围内。