快排(QuickSort)

快排是经典的二分法思想的排序方法, 它是不稳定的(即a0, a1的值均为1, 但是排序后可能a1在a0前面, 不保证相对顺序不变).

输入: 数组A, 长度为L. 
输出: 排序后的数组A.
基本思想: 
	①select pivot: 从输入数组中随机取一个数字作为基准(pivot);
	②partition: 将所有<pivot的数字放到pivot左边, 记为子数组A_left, 
	所有>pivot的数字放到pivot右边, 记为A_right;
	③recursion: 对子数组A_left和A_right递归的调用步骤①和步骤②.
  经典的方法和荷兰国旗法的区别在于②, 经典方法是返回一个position,
所有position左边的数字都<=pivot, position右边的数字都>pivot, 
position本身的值==pivot; 而荷兰国旗法返回的是一个开区间(left, right),  
left左边包括自身的值都<pivot, right右边包括自身的值都>pivot, 
而区间内的值都==pivot. 效率更高.

代码实现(python, 荷兰国旗法)

def swap(A, i, j):
	tmp = A[i]
	A[i] = A[j]
	A[j] = tmp

def partition(A, start, end):
    left = start - 1
    right = end
    pivot = A[end-1]
    k = start
    while k < right:
        if A[k] == pivot:
            k += 1
        elif A[k] < pivot:		# 将碰到的<pivot的值放到left控制的左半部分
            left += 1
            swap(A, k, left)
            k += 1
        else:					# 将碰到的>pivot的值放到right控制的右半部分
            right -= 1
            swap(A, k, right) 
    return left, right
    
def QSort(A, start, end):
	if start < end:
		left, right = partition(A, start, end) 
		QSort(A, start, left+1)
		QSort(A, right, end)```