快速排序思想：
1.从数组中取出一个元素记为i，将数组划分为两个部分，前半部分所有元素比该元素小，后半部分的所有元素比该元素大。
2.将i放置在两部分之间，对前半部分与后半部分递归进行第一步直至数组长度为1，排序完成。
快速排序时间复杂度：
当第一步划分的两个部分其中一个部分包含了n-1个元素，另一部分包含0个元素时为最坏情况。如果每一层递归上的划分都是最大程度不平衡的，此时快速排序的时间复杂度为Θ(n2)。
当第一步划分的两个部分其中一个部分包含了n/2个元素，另一部分包含n/2-1个元素时为最好情况。如果每一层递归上的划分都是最大程度平衡的，此时快速排序的时间复杂度为Θ(nlgn)。
快速排序的平均运行时间更接近于最好情况，只要划分是常数比例的，算法的运行时间总是O(nlgn)。
快速排序代码示例：
import random def quick_sort(a,i,j): if i < j: q = partition(a,i,j) quick_sort(a,i,q-1) quick_sort(a,q+1,j) def partition(a,i,j): ret = i - 1 for k in range(j-i): if a[i+k] < a[j]: ret += 1 tmp = a[i+k] a[i+k] = a[ret] a[ret] = tmp ret += 1 tmp = a[j] a[j] = a[ret] a[ret] = tmp return ret def main(args): a = [] for i in range(100): a.append(random.randint(1,100)) print(a) quick_sort(a,0,len(a)-1) print(a) return 0 if __name__ == \'__main__\': import sys sys.exit(main(sys.argv))