快速排序 及其 优化

快速排序是基于分治思想的排序算法，核心是划分与递归，不需要额外的辅助空间。

快排的基本实现

def  partition(ls,l,r):  # 一次交换，返回交换后的中轴位置
    middle = l  # 随机选取中轴值，这里选取第一个元素
    while l<r:
        while not ls[r] <= ls[middle] and l<r:   #高指针先走
            r-=1
        while not ls[l] > ls[middle] and l<r:
            l+=1
        ls[l],ls[r] = ls[r],ls[l]   # 交换
    ls[middle],ls[r] = ls[r],ls[middle]  # 中轴值到中轴位置
    return l

def  doSort(ls,l,r):
    if l>=r:    # 终止递归
        return ls
    m = partition(ls,l,r)
    print('ls {}  l {}  m {}  r {}'.format(ls,ls[l],ls[m],ls[r])) 
    doSort(ls,l,m-1)
    doSort(ls,m+1,r)

#l = [6,2,7,3,11,11,11,8,9,1,11,5]
l = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
doSort(l,0,len(l)-1)
print(' return_list {}'.format(l))

1.保持随机性

切分元素需要保持是随机的，即doSort 对所有子数组是一视同仁的，所以我们可以在 doSort前打乱数组元素

快排为啥需要随机？

l = [5,1,9,3,7,4,8,6,2]
$ python QuickSort.py
after one partition ls:[4, 1, 2, 3, 5, 7, 8, 6, 9] l:4 m:5 r:9
after one partition ls:[3, 1, 2, 4, 5, 7, 8, 6, 9] l:3 m:4 r:4
after one partition ls:[2, 1, 3, 4, 5, 7, 8, 6, 9] l:2 m:3 r:3
after one partition ls:[1, 2, 3, 4, 5, 7, 8, 6, 9] l:1 m:2 r:2
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:6 m:7 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:8 m:8 r:9
 return_list [1, 2, 3, 4, 5, 6, 7, 8, 9]

这里我们讨论下qs时间复杂度最好的情况，即每次划分后都能正好把数组对半分，这时满足 分治递归 C（n） = 2 C(n/2) + n

其中 2 C下标n/2 表示将两个子数组排序的成本，N 表示切分元素和所有元素进行比较的成本 不难得出 C(n) ~ nlogn

最坏情况

l = [1,2,3,4,5,6,7,8,9]
$ python QuickSort.py
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:1 m:1 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:2 m:2 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:3 m:3 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:4 m:4 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:5 m:5 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:6 m:6 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:7 m:7 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:8 m:8 r:9
 return_list [1, 2, 3, 4, 5, 6, 7, 8, 9]

最坏情况下时间复杂度 划分比较的次数为 n、n-1 、n-2、... 1
时间复杂度为 O(n^2)

为了避免在 数组几乎有序的情况下时间复杂度退化到 O(n^2)，保持数组的随机性就比较重要了，我们在第一个划分前 先随机打乱数组元素。

import random 
l =[1,2,3,4,5,6,7,8,9]
random.shuffle(l)
doSort(l,0,len(l)-1)

2. 小数组时切换成 插入排序

#  实现快排
import random  
# 快排划分方法
def  partition(ls,l,r):  # 一次交换，返回交换后的中轴位置
    middle = l  # 随机选取中轴值，这里选取第一个元素
    while l<r:
        while not ls[r] <= ls[middle] and l<r:   #高指针先走
            r-=1
        while not ls[l] > ls[middle] and l<r:
            l+=1
        ls[l],ls[r] = ls[r],ls[l]   # 交换
    ls[middle],ls[r] = ls[r],ls[middle]  # 中轴值到中轴位置
    return l

# 插入排序
def insertSort(ls,l,r):
    for i in range(l+1,l+len(ls[l:r+1])):
        j = i-1
        while j >=l and not ls[j]<= ls[j+1]:
            ls[j],ls[j+1] = ls[j+1],ls[j] #交换操作
            j -=1
# ★★★优化:小数组切换为插入排序的快排
def  QuickSort(ls,l,r):
    M = 5  # 阈值推荐在  5到 15之间
    if l + M>=r :   # 终止递归
        insertSort(ls,l,r)
        return ls
    m = partition(ls,l,r)
    QuickSort(ls,l,m-1)
    QuickSort(ls,m+1,r)

l = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48,6,3,23,11,12,13,62,55,134,2324343,33,98,1,6]
random.shuffle(l)    #  ★★★优化:排序前随机化数组
QuickSort2(l,0,len(l)-1)
print(' return_list {}'.format(l))