1.快速排序是神马？
快速排序使用[分治法]（Divide and conquer）策略来把一个[序列]（list）分为两个子序列（sub-lists）。它的实现步骤如下：
- 从数列中挑出一个元素，称为“基准”（pivot)
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
快速排序
2. Talk is cheap, show me the code
- python简单写法。 为了方便看清楚快排如何运行，写看精简写法。不得不说python确实比较适合写算法。
def quickSort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot] #将小于等于pivot的元素放入less数组中
greater = [i for i in array[1:] if i > pivot] #将大于pivot的元素放入greater数组中
return quickSort(less) + [pivot] + quickSort(greater) # 递归执行
print(quickSort([3,1,2,5,1123,1,5123,63523,123,4,768,9,23]))
image.png
- 原地排序
def quick_sort(lst):
lst = lst[:] #将切片后的值付给lst，修改lst不会影响原数组
n = len(lst)
def partition(lst,start,end):
i = start - 1 # 重点 i 的取值应该从分组后的元素开始
pivotIndex = end
pivot = lst[end]
for j in range(start,end):
#重点在这里，中间值去的是最有一个元素，从前向后遍历数组，如果小于中间值，把元素往前挪（放置在下标为i的地方，i是每次加1的）
# [ 5, 1, 5, 0, 1, 2, 4] （5 < 4 false）
# [ 1, 5, 5, 0, 1, 2, 4] (1 < 4 true )
# [ 1, 5, 5, 0, 1, 2, 4]
# [ 1, 0, 5, 5, 1, 2, 4]
# [ 1, 0, 1, 5, 5, 2, 4]
# [ 1, 0, 1, 2, 5, 5, 4]
if lst[j] < pivot:
i = i + 1
lst[i],lst[j] = lst[j],lst[i]
lst[i+1],lst[pivotIndex] = lst[pivotIndex],lst[i+1]
return i+1
def sort(lst,start,end):
if start >= end:
return
p = partition(lst,start,end)
sort(lst,start,p-1)
sort(lst,p+1,end)
sort(lst,0,n-1)
return lst
