一、 快速排序与归并排序的比较
快速排序的最快的时间复杂度为O(n)，最差情况下的时间复杂度为O(n^2)，平均的时间复杂度为O(nlgn);
归并排序的时间复杂度在任何情况下都是O(nlgn);
快速排序的时间复杂度计算
每一轮快速排序的时间负责度都是O(n), 平均一共有lgn轮，故整体的平均时间复杂度为O(nlgn)；
二、 快速排序思想
- 循环不变式：每一轮针对比较的值，在一轮完成之后，会移动到最终正确的位置。
- 排序特点：对于其中被选取参与排序的元素N，当其针对的排序完成后，左侧的元素都小于（大于）等于该元素，右侧的元素都大于（小于）等于该元素；
- 快排经典变种简化：Kth-max问题。
- 快速排序是的时间复杂度是平均时间复杂度，不同的初始情形，快排的时间复杂度不同。快排最差的情况有一下三种
（1）数组倒序有序;
（2）数组倒序有序;
（3）所有的元素都相同（1、2的特殊情形）
三 快速排序实现代码
# coding=utf-8
# environment: python3
def sort(array, low ,high):
pivot = array[low]
while low < high:
while low < high and array[high] >= pivot:
high -= 1
while low < high and array[low] <= pivot:
low += 1
array[high] = array[low]
array[low] = pivot
return low
def quick_sort(array, low, high):
# init the recursive function.
if low < high:
pivot_loc = subsort(array, low, high)
quick_sort(array, low, pivot_loc-1)
qucik_sort(array, pivot_loc+1, high)
if __name__ == "__main__":
array = [49,38,65,97,76,13,27]
print(array)
# round 1 [38, 13, 27, ]
quick_sort(array,0,len(array)-1)
# after sort: [13, 27, 38, 49, 65, 76, 97]
print(array)
四、 引申：Kth-Max问题思考
利用快排思路解决Kth-Max问题：
这里假设其中一个参与的元素X，其对应的下标为X.index；
由前文可知，每一轮快排都会使当前的元素N放置到最终的正确位置中，且左边的数字都小于等于X，右边的元素都大于等于X，故考虑元素X的位置，有以下三种情形：
- 若X的下标（降序排序）等于K，则X左方加上X本身为整个数组最大的K个元素，满足问题需求，返回结果；
- 若X的下标（降序排序）大于K，则针对下标范围为[X.index+ 1 : K]的子数组进行快速排序，直到满足要求1；
- 若X的下标（降序排序）小于K，则针对下标范围为[K + 1 : ]的子数组进行快速排序，直到满足要求1；
综上，当数组长度为N时，Kth-Max算法采用快排思想，平均的时间复杂度为(N/2 + N/4 + N/8 + ... + N/2^i)，易证时间复杂度为O(N)。
