O(nlogn)就地排序算法

Question

这个问题是在我的计算机科学入门期中考试准备的。

有一种算法可以在O(n)时间内找到列表中的kth元素，并假定它已经就位。使用该算法，编写一个在最坏情况下运行的就地排序算法O(n*log(n))，并证明了它的有效性。既然这个算法存在，为什么还会使用mergesort呢？

我假设我必须编写一些快速排序算法的替代形式，这是O(n^2)的最坏情况，因为合并排序不是就地算法。让我困惑的是在列表中找到kth元素的给定算法。通过数组的元素进行简单的循环迭代不是一个O(n)算法吗？

如果所提供的算法不改变执行时间内的任何内容，它如何能使排序算法的运行时间有任何不同？我不知道如何使用快速排序，插入排序或选择排序，它可能会降低到O(nlogn)最坏的情况。任何输入都是非常感谢的！

Answer 1

检查维基，即“按排序选择”部分：

同样地，给出一个中值选择算法或一般选择算法来寻找中值，人们可以用它作为快速排序的枢轴策略，得到排序算法。如果选择算法是最优的，意味着O( n)，则结果排序算法是最优的，意味着O(n log )。中值是排序的最佳枢纽，因为它平均地分配数据，从而保证最优排序，假设选择算法是最优的。使用快速排序中的枢轴策略(近似中值)，存在对中间值中值的排序模拟，并且类似地产生最优的快速排序。

简单地说，在某些情况下，合并优先于快速排序，原因是它是稳定的 (而快速排序不是)。

Answer 2

合并排序的原因。合并排序是稳定的。合并排序比快速排序做更多的移动，但比快速排序更少。如果比较开销大于移动开销，那么合并排序会更快。比较开销可能更大的一种情况是对指向对象的索引或指针数组进行排序，例如字符串。

如果对链接列表进行排序，那么使用指向工作列表的第一个节点的指针数组进行合并排序是我所知道的最快的方法。HP / Microsoft：：list：：sort()就是这样实现的。在指针数组中，arrayi为NULL或指向长度为pow(2，i)的列表(除非最后一个指针指向无限长度的列表)。

Answer 3

我找到了解决办法：

if(start>stop)                              2 op.                                                           
    pivot<-partition(A, start, stop)        2 op. + n
    quickSort(A, start, pivot-1)            2 op. + T(n/2)
    quickSort(A, pibvot+1, stop)            2 op. + T(n/2)

T(n)=8+2T(n/2)+n            k=1
    =8+2(8+2T(n/4)+n/2)+n
    =24+4T(n/4)+2n          K=2
    ...
    =(2^K-1)*8+2^k*T(n/2^k)+kn

Recursion finishes when n=2^k <==> k=log2(n)

T(n)=(2^(log2(n))-1)*8+2^(log2(n))*2+log2(n)*n
    =n-8+2n+nlog2(n)
    =3n+nlog2(n)-8
    =n(3+log2(n))-8
    is O(nlogn)