快速排序的几种pivot基数选择方法

import random

def quick_sort(nums, l, r):
    if l >= r:
        return
    pivot = partition_l(nums,l,r)   #可切换以下不同基数选择方法
    quick_sort(nums,l,pivot-1)
    quick_sort(nums,pivot+1,r)
'''
random pivot 随机基数
'''
def partition_ran(nums,l,r):
    pivot = random.randrange(l,r+1)
    nums[pivot],nums[r] = nums[r],nums[pivot]
    i = l-1
    for j in range(l,r):
        if(nums[j]<nums[r]):
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i+1], nums[r] = nums[r], nums[i+1]
    return i + 1


'''
leftmost as pivot  最左边元素为基数
'''
def partition_l(nums,l,r):
    i = l
    for j in range(l+1,r+1):
        if nums[j] < nums[l]:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[l] = nums[l], nums[i]
    return i



'''
rightmost as pivot  最右边元素为基数
'''
def partition_r(nums,l,r):
    i = l - 1
    for j in range (l,r):
        if nums[j] < nums[r]:
            i += 1
            nums[i],nums[j] = nums[j],nums[i]
    nums[i+1],nums[r] = nums[r],nums[i+1]
    return i + 1

a = random.sample(range(0,10),6)
print("original%s"%a)
quick_sort(a,0,len(a) - 1)
print("answer%s"%a)

partition中的index非常易错。

而分别以左右元素为基数时的两种快排，看似相似，实际上index有差别，（主要是最后pivot是和i还是i+1交换，注意到 i作为维持partition的分界线，i 左边的元素都比pivot小，i 右边的元素都比pivot大。

以右pivot为例子，与右pivot交换的必定是i右边的元素，否则的话不能维持右侧parition都大于pivot的性质）稍微没捋对就会出错。

随机基数快排：随机选取index，然后和最左或者最右元素交换，转换成已解决的问题。随机基数下我们期望平均情况下对数组的paritition比较均衡，并且对一些极端例子的最坏情况下的处理会更好。