Qs&tree

快速排序与二叉树分析

复习快排的时候想到的,这里记录一下。

先看一下比较容易理解的快排算法(摘自维基):

 function quicksort(q)
 {
     var list less, pivotList, greater
     if length(q) ≤ 1 
         return q
     else 
     {
         select a pivot value pivot from q
         for each x in q except the pivot element
         {
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         }
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }
 }

稳定性

大家都说快排是不稳定的,想到个算法,发现和知乎这个问题一致:https://www.zhihu.com/question/45929062 不难发现,对于上面这个简单的快排算法来说,这种优化使得其是稳定的。 高票的回答应该是指复杂版的in-place算法。

空间复杂度

对于in-place算法来说,因为相关操作是在原List进行的,所以空间复杂度是O(n)。

时间复杂度

我们可以模拟一下排序的过程,第一轮各元素与pivot比较时,总共需要n次比较操作。 第二轮比较时,左边的元素需要与左边的pivot比较,右边的元素需要与右边的pivot比较,总共也需要n次比较操作。 这样,做多少轮比较,时间复杂度就是多少。因快排将队列分成了左边和右边,也即是说可以将这个过程想像成一颗二叉树。在最好的情况下,就是树的深度最欠的情况,需要log n轮。在最快的情况下,树退化成列表,需要n轮。所以最好和最坏的复杂度分别为n*log n和n^2。在平均情况下,这还是一颗二叉树,深度差不多也是log n(乘以一个系数?)。

完。