python快速排序

探究快速排序及三路快速排序的应用场景
在对近乎有序或相同元素很多的列表进行排序时，如果不进行调优，快速排序会接近o(n2)的速度。
而三路快排，在三种情况下都表现稳定。

from functools import wraps
import time,random
def timeer(name):
    def decorator(func):
        @wraps(func)
        def wrapper(*args,**kwargs):
            start = time.time()
            result = func(*args,**kwargs)
            end = time.time()
            print(name+'耗时:',end-start)
            return result
        return wrapper
    return decorator

class QuickSort:
    def __init__(self,arr):
        assert isinstance(arr,list)
        self.arr = arr
        self.l = 0
        self.r = len(arr)-1

    @timeer('单路快排')
    def quickSort(self):
        self._quickSort(self.arr,self.l,self.r)

    @timeer('三路快排')
    def quickSort3(self):
        self._quickSort3(self.arr,self.l,self.r)

    def _quickSort(self,arr,l,r):
        if r-l<=20:  #当小列表小于等于20时选择插入排序直接修改好，减少递归次数
            insertionSort(arr,l,r)
            return
        index = self._partition(arr,l,r)
        self._quickSort(arr, l, index - 1)
        self._quickSort(arr, index + 1, r)


    def _partition(self,arr,l,r): #单路快排：返回的j,保证位置j左边的值都小于arr[j],右边的值都大于arr[j]
        start = arr[l]
        j = l
        for i in range(l+1,r+1):
            if arr[i] < start:
                j+=1
                arr[i],arr[j] = arr[j],arr[i]
        arr[j],arr[l] = arr[l],arr[j]
        return j


    def _quickSort3(self,arr,l,r): #三路快排:适用于列表中有很多重复值且列表近似于有序的情况
        if r-l<=20:  #当小列表小于等于20时选择插入排序直接修改好，减少递归次数
            insertionSort(arr,l,r)
            return
        temp = random.randint(l, r)
        arr[l], arr[temp] = arr[temp], arr[l]  #随机打乱标记数,防止arr为有序数组的速度降为o(n)
        start = arr[l]
        lt = l  ## arr[l + 1...lt] < start
        gt = r + 1 ## arr[gt...r] > start
        i = l + 1 ## arr[lt + 1...i) == start
        while i < gt:
            if  arr[i] < start:
                arr[lt + 1],arr[i] = arr[i],arr[lt+1]
                i+=1
                lt+=1
            elif  arr[i] > start:
                arr[i], arr[gt-1]=arr[gt-1],arr[i]
                gt -= 1
            else: ##arr[i] == start
                i += 1
        arr[l], arr[lt] = arr[lt],arr[l]
        self._quickSort3(arr, l, lt - 1)
        self._quickSort3(arr, gt, r)


    def test(self):
        for i in range(0,len(self.arr)-1):
            if not self.arr[i]<=self.arr[i+1]:
                print ('错误排序')
                return
        print ('正确排序')

def insertionSort(arr,l,r):  ##对arr[l...r]范围的数组进行插入排序
    for i in range(l+1,r+1):
        key = arr[i]
        j = i - 1
        while j >= l and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


if __name__ == "__main__":
    n = 100000
    import sys
    sys.setrecursionlimit(100000)  # 增加递归上限

    print ('近乎有序的列表')
    arr = [i for i in range(0,n)]
    for i in range(0,100): #乱序1000次,近乎有序
        ran1 = random.randint(0, n-1)
        ran2 = random.randint(0, n-1)
        arr[ran1],arr[ran2]=arr[ran2],arr[ran1]
    quick = QuickSort(arr)
    quick3 = QuickSort(arr)
    quick.quickSort()
    quick3.quickSort3()

    print ('有很多相同元素的列表')
    arr = [random.randint(1,100) for i in range(0,n)]
    quick = QuickSort(arr)
    quick3 = QuickSort(arr)
    quick.quickSort()
    quick3.quickSort3()

    print ('正常乱序列表')
    arr = [random.randint(1,n) for i in range(0, n)]
    quick = QuickSort(arr)
    quick3 = QuickSort(arr)
    quick.quickSort()
    quick3.quickSort3()

output:
近乎有序的列表
单路快排耗时: 30.255020141601562
三路快排耗时: 1.1872174739837646
有很多相同元素的列表
单路快排耗时: 5.690019845962524
三路快排耗时: 0.374910831451416
正常乱序列表
单路快排耗时: 0.6248507499694824
三路快排耗时: 1.1715974807739258