先放一段python 跑跑
本段只说递归方式的：
L = [5, 2, 0, 7, 3, 8, 9, 4, 2, 1] def quick_sort(L, low, hight): i = low j = hight if i >= j: return L key = L[low] while i<j: # 本L的左右拆分整理 while i<j and key <=L[j]: j-=1 L[i] = L[j] # i=i+1 # 错误, 因为 i=j的时候,while 不循环,但是 i=i+1产生了副作用 while i<j and key >= L[i]: i+=1 L[j] = L[i] # j = j-1 L[i] = key quick_sort(L, low, i-1) # left sort quick_sort(L, j+1, hight) # right sort return L quick_sort(L, 0, len(L)-1)
描述， 首选选择第一个数作为key基础，将L拆分成右边大于key，左边小于key
- 第一个L[i]数取出来做key，此时i的位置空出来留给 从右边开始遍历到的第一个小于key的数；
- 找到该数j后， j的数值放到i上，j空出来了，从i向右遍历，找出第一个大于key的数来填充j；
- i=j 以后，说明我们描述工作完成了， 后面在对左右两边进行 相同的整理；
不稳定，因为左右两边的位置会经常互换
如果数组已经有序时，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为Θ(n^2)。
平均时间复杂度：尽管快速排序的最坏时间为 O(n^2 ), 但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快的，快速排序亦因此而得名。它的平均时间复杂度为 O(n×lgn)。
空间复杂度：快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为 O(lgn), 故递归后所需栈空间为 O(lgn) 。最坏情况下，递归树的高度为 O(n), 所需的栈空间为 O(n) 。