#
快速排序算法（quick sort）
下文简称“快排”。
快排算法的实现，在Python中有偷懒的做法，就是不对传入数组进行原地分区，show me the code:
# 快排实现之邀请面试官拷打版本
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
less = [x for x in arr[:-1] if x <= pivot]
greater = [x for x in arr[:-1] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
Ier：您这个实现看起来挺简洁嘛，说说看这么做有什么不足的地方？最差情况是什么？
Iee：嗯，您是指，啊，对了，嗯（笑容逐渐凝固.gif，磨磨叽叽假装思考...）
Ier: 我是指您代码里使用了额外的存储空间，`less` 和 `greater`，可以不用它们吗？
Iee：哦，您是指要对数组进行原地分区吗？（那些追求速度和基情的编程语言通常都是原地操作：应该是问这个吧？）
Ier: 对。
Iee：（心里嘀咕，就是怕那个 `partition()` 函数，怕啥来啥是吧:(，墨菲）
def quick_sort(arr):
if len(arr) <= 1:
return arr
low, high = 0, len(arr)-1
quick_sort_inplace(arr, low, high)
def quick_sort_inplace(arr, low, high):
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort_inplace(arr, low, pivot_idx-1)
quick_sort_inplace(arr, pivot_idx+1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i + 1]
return i+1
Ier: 嗯，好。您的pivot是怎么选择的啊？
Iee：我是选了数组的最后一个元素。
Ier：嗯，那我有个问题请教一下，如果最后一个元素恰好是最大值或最小值的话，会怎么样？
Iee：（是啊，我也不太理解为什么这么草率地用最后一个元素呢？）嗯，啊，这个，应该是会导致分区效果不好吧。
Ier: 那还可以优化吗？
Iee：随机选择一个元素作为pivot？
好，要的就是这个“随机选择“。（顺便结束面试拷打模拟：)