1 引言

如题目所示，本节的精华在于用数学解决一个直觉上看似纷乱复杂的问题，里面有一些一般性的分析方法，如引入Indicator变量，从而把不确定问题引入到概率框架进行分析，一步一步把直觉上混乱的问题理清楚，数学之美也就是如此吧！

如果有个算法在某些情况下表现的很差，在某些情况下又表现的不错，那么你还会放心的使用该算法吗？通过下面的分析后你会很放心使用快速排序算法。

2 Quicksort

2.1 算法描述

2.2 手工演示

• 指针$i$指示的是$\le pivot$的最后一个，作用是是用来标记$\le pivot$和$\ge pivot$的分割状态，指针$j$用来遍历所有元素，每遍历一个元素都会和$pivot$比较，不断更新$i$的指示状态。
  

2.3 实现

# -*- coding: utf-8 -*-def PARTITION(A, p, r):x = A[r]i = p - 1for j in range(p, r):if A[j] <= x:i = i + 1A[i], A[j] = A[j], A[i]A[i + 1], A[r] = A[r], A[i + 1]return i + 1def QUICK_SORT(A, p, r):if p < r:q = PARTITION(A, p, r)QUICK_SORT(A, p, q - 1)QUICK_SORT(A, q + 1, r)if __name__ == '__main__':A = ['x', 2, 8, 7, 1, 3, 5, 6, 4]print('before sort:', A[1:])QUICK_SORT(A, 1, len(A) - 1)print('after sort:', A[1:])

运行结果：

before sort: [2, 8, 7, 1, 3, 5, 6, 4] after sort: [1, 2, 3, 4, 5, 6, 7, 8]

3 Analysis of quicksort

3.1 worst case

用递归树分析如下：

3.2 best case

应用主定理容易得到$T(n)=\Theta (nlogn)$。

3.3 $\frac{1}{10},\frac{9}{10}$case

下面看一种感觉直觉上很差，其实效果很好的情况。

使用递归树分析：

• 注意$lo{g}_{\frac{10}{9}}n/lo{g}_{2}n=lo{g}_{\frac{10}{9}}2$，这是一个常数。

3.4 worst best交替情况

• 好坏交替的情况下，最后仍然是好的！

3.5 random case

上面从矛盾的特殊性上让直觉有一个直观的感受，只要不是特别极端（如一个初始状态是逆序的数列），貌似大部分情况下都是ok的，下面用概率框架确认这种直观的感觉是正确的。

• 对于离散不确定问题，要引入概率框架进行讨论，首先要引入一个合适的随机变量，这里引入指示器（Indicator）随机变量，这个变量在机器学习算法中使用更为广泛，看似简单的一个定义，却可以化繁为简的用一个表达式表示所有情况。
  

• 至此，已经进入到概率框架，可以暂时忘记之前的算法问题背景：
  

• 概率世界都是是不确定的，研究概率大目的是找出不确定问题的平均特性，如期望、方差等，这里只关注期望。

• 下面的推到中用到了期望的线性可加性和独立可乘性。

分割的独立性：第一次分割后，数组分为第a部分和第b部分，a部分具体在哪个位置分割已经和第一次分割没有关系。

• 猜想$E[T(n)]\le anlgn$，a足够大，接下来数学归纳法要登场了！，首先有一个数学事实要知道，这个结论也是用数学归纳法容易证明：
  

• 使用数学归纳法证明$E[T(n)]\le anlgn$
  

4 总结

• 从上面的分析中可以看到，快速排序大概率是$\Theta (nlogn)$的，在实际应用中快速排序往往是归并排序速度的2倍以上，如果在细节上对算法微调，则可以表现出更好的性能.

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的六、Analysis of quicksort的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。