我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
答案将略微倾向于快速排序w.r.t的变化带来的DualPivotQuickSort的基本值。它在JAVA 7中用于在JAVA .util. arrays中排序
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
您可以在这里找到JAVA7实现- http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java
关于DualPivotQuickSort的进一步精彩阅读- http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
其他回答
与归并排序不同,快速排序不使用辅助空间。而归并排序使用辅助空间O(n)。 归并排序的最坏情况时间复杂度是O(nlogn)而快速排序的最坏情况复杂度是O(n²)这发生在数组已经排序的时候。
正如许多人所注意到的,快速排序的平均情况性能要比归并排序快。但这只适用于假设按需访问任何内存段的时间为常数的情况。
在RAM中,这种假设通常不太坏(由于缓存的存在,这种假设并不总是正确的,但也不太坏)。然而,如果你的数据结构足够大,可以存储在磁盘上,那么快速排序就会因为磁盘平均每秒进行200次随机查找而被扼杀。但是,同样的磁盘在按顺序每秒读取或写入兆字节的数据方面没有任何问题。这正是归并排序所做的。
因此,如果数据必须在磁盘上排序,你真的,真的想使用归并排序的一些变体。(通常你快速排序子列表,然后开始将它们合并到某个大小阈值以上。)
Furthermore if you have to do anything with datasets of that size, think hard about how to avoid seeks to disk. For instance this is why it is standard advice that you drop indexes before doing large data loads in databases, and then rebuild the index later. Maintaining the index during the load means constantly seeking to disk. By contrast if you drop the indexes, then the database can rebuild the index by first sorting the information to be dealt with (using a mergesort of course!) and then loading it into a BTREE datastructure for the index. (BTREEs are naturally kept in order, so you can load one from a sorted dataset with few seeks to disk.)
在许多情况下,了解如何避免磁盘寻道使我将数据处理工作花费数小时而不是数天或数周。
That's hard to say.The worst of MergeSort is n(log2n)-n+1,which is accurate if n equals 2^k(I have already proved this).And for any n,it's between (n lg n - n + 1) and (n lg n + n + O(lg n)).But for quickSort,its best is nlog2n(also n equals 2^k).If you divide Mergesort by quickSort,it equals one when n is infinite.So it's as if the worst case of MergeSort is better than the best case of QuickSort,why do we use quicksort?But remember,MergeSort is not in place,it require 2n memeroy space.And MergeSort also need to do many array copies,which we don't include in the analysis of algorithm.In a word,MergeSort is really faseter than quicksort in theroy,but in reality you need to consider memeory space,the cost of array copy,merger is slower than quick sort.I once made an experiment where I was given 1000000 digits in java by Random class,and it took 2610ms by mergesort,1370ms by quicksort.
同时考虑时间和空间的复杂性。 归并排序: 时间复杂度:O(nlogn), 空间复杂度:O(nlogn)
快速排序: 时间复杂度:O(n²), 空间复杂度:O(n)
现在,他们各自在一个场景中获胜。 但是,使用随机枢轴,您几乎总是可以将快速排序的时间复杂度降低到O(nlogn)。
因此,在许多应用中,快速排序是首选,而不是归并排序。
我想补充的是,到目前为止提到的三种算法(归并排序,快速排序和堆排序)只有归并排序是稳定的。也就是说,对于那些具有相同键的值,顺序不会改变。在某些情况下,这是可取的。
但是,说实话,在实际情况下,大多数人只需要良好的平均性能和快速排序…快速=)
所有排序算法都有其起伏。有关排序算法的概述,请参阅维基百科的文章。