1回答

liuyubobobo

2016-11-09

1

归并排序的一大特点就是非原地排序。所以近乎在所有的教科书上，归并排序的空间复杂度都是O(n)的。如果你找到了非常好的能够不需要辅助的数组空间而简便进行归并排序的方法，应该说算是很厉害的发现哦！

2

判断算法的速度，不能简单地只看for循环的层数，还要看循环的增量。

for(int i = 0 ; i < n ; i ++ )
for(int i = 0 ; i < n ; i +=i )

上面的两个循环，有着本质的不同。第一个循环运行n次，第二个循环只运行log(n)次，虽然他们都是for循环的形式！

最简单的判断方式是：把循环展开，当做加法，具体分析一下这个循环到底执行了多少次。可以先从小样本开始，比如只针对8个或者16个数据作分析，再把结论推而广之，放到n个样本中。这是一个很有意义的深入研究算法执行过程的练习。如果自己实在用笔算不明白，也可以用程序做一个实验，在循环内加入一个执行计数期，让程序帮你计数一下到底那个O(1)的操作执行了几次。

按照这样的分析，你就会看到，在自底向上的归并算法中，我们用循环制作了一个nlogn的排序。

3

真正评判算法的性能效率是一个很复杂的事情。我们在课程中所讲解的时间复杂度，通常被称为平均时间复杂度。也就是在“平均情况”下算法的性能。但是什么叫“平均情况”，在很多时候也很难定义。不过对于排序算法来说，可以这么理解平均情况：待排序数组越随机越好；待排序数组的元素个数越多越好。

另外，只运行一次算法也可能存在性能的偏差，尤其是我们的测试用例是随机生成的。因此，可以多次运算算法，取运行时间的平均值作为最终评判算法性能的标准。

为此，我做了一个测试用例，对100万的数据分别进行MergeSort和ShellSort100次，取平均值作为最终的结果。你可以在这里下载到我的测试代码：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/03-Sorting-Advance/MergeSortAndShellSort

我的测试结果如下，可以看出，MergeSort是胜出的。

Sorting 1000000 elements 100 times. Calculate the average run time.
Merge Sort Average Run Time: 0.333454 s
Shell Sort Average Run Time: 0.584991 s

为什么有的时候，我们会看到ShellSort比MergeSort，甚至QuickSort更快？这是有可能的。原因如下：

1）数据相对有序。像我在课程里讲的，面对完全有序的数组，InsertionSort可以变成一个O(n)的算法，这是MergeSort和QuickSort都望尘莫及的。ShellSort作为InsertionSort推导出的算法，也继承了这一优势。在数据相对有序的情况下，ShellSort有优势。

2）数据量太小。我们看到，对于小数据，我们愿意用InsertionSort优化，就是这个原因。这是因为对于算法复杂度，前面还有一个常数。而MergeSort的这个常数相对较大。换句话说：如果一个算法是O(nlogn)的，但实际是100*nlogn的；另一个算法是O(n^2)的，但是是2*n^2的，如果我们取n=100，就会发现2*n^2是快于100*nlogn的。也就产生了一个O(n^2)的算法快于一个O(nlogn)算法的印象。这也就是为什么，我们要真正看到算法性能，需要大数据量的原因。事实上，用算法做性能优化，也是为了解决大数据量带来的问题。对于现代计算机而言，即使使用选择排序对100个元素进行排序，完全不是什么问题。

3）MergeSort和QuickSort是递归实现。递归实现比直接进行的循环迭代实现需要耗费额外的性能做递归调用。

有兴趣的话，你也可以具体测一测，在你的计算机上，n从多大开始，MergeSort就显著快于ShellSort了。如果数组近乎有序，又有什么不同？相信是很有意义的实验，也会让你对这些排序算法有更深入的理解。

1

0