1.快速排序定义：
快排的主要思想：分治+迭代，只需要三步：
2.时间复杂度：
时间复杂度：快排的时间复杂度为O(nlogn)
空间复杂度：排序时需要另外申请空间，并且随着数列规模增大而增大，其复杂度为：O(nlogn)
3.稳定性：
不稳定（比如基准值的前后都存在与基准值相同的元素，那么相同值就会被放在一边，这样就打乱了之前的相对顺序）
4.与归并排序的区别：
归并排序与快排两种排序思想都是分而治之，但是它们分解和合并的策略不一样：归并是从中间直接将数列分成两个，而快排是比较后将小的放左边大的放右边，所以在合并的时候归并排序还是需要将两个数列重新再次排序，而快排则是直接合并不再需要排序，所以快排比归并排序更高效一些。
5.面试
6.Python代码：
1 #coding:utf-8 2 3 def parttion(v, left, right): 4 ‘‘‘ 5 :param v: 要排序的列表 6 :param left: 列表起始端 7 :param right: 列表末端 8 :return: 9 ‘‘‘ 10 key = v[left] #基准 11 low = left 12 high = right 13 while low < high: 14 while (low < high) and (v[high] >= key): 15 high -= 1 16 v[low], v[high] = v[high],v[low] 17 while (low < high) and (v[low] <= key): 18 low += 1 19 v[high],v[low] = v[low],v[high] 20 v[low] = key 21 return low 22 def quicksort(v, left, right): 23 if left < right: 24 p = parttion(v, left, right) 25 quicksort(v, left, p-1) 26 quicksort(v, p+1, right) 27 return v 28 29 s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6] 30 print("before sort:",s) 31 s1 = quicksort(s, left = 0, right = len(s) - 1) 32 print("after sort:",s1)
输出结果：
原文：https://www.cnblogs.com/xiaodangdang/p/13207598.html