2020-03-24

针对随机选择，试验了几种写法的速度，
但面临的数据中，明确告知存在大量重复元素是，还是选用三向切分吧
列表的数据做了删减，着急写，单词有些未写全；r=right

'''
a=[9,7,4,3,5,6,2,8,1,3,1,1,3,4,2,3,4,1,3,2,4,2,3,4,1,]
def pp(a,left,r):
    if left==r:return left
    e=r
    key=a[r]
    while left<r:
        while a[left]<=key and left<r:
            left+=1
        while a[r]>=key and left<r:
            r -=1
        a[left],a[r]=a[r],a[left]
    a[left],a[e]=a[e],a[left]
    return left

def pp(arr,left,r):
    temp=r
    key=arr[r]
    slow=left
    for fast in range(left,r):
        if arr[fast]<=key:
            arr[fast],arr[slow]=arr[slow],arr[fast]
            slow+=1
    arr[slow],arr[temp]=arr[temp],arr[slow]
    return slow
'''
def pp(L, left, right):
    pivotkey = L[right]
    while left < right:
        while left < right and L[left] <= pivotkey:
            left += 1
        L[right] = L[left]
        while left < right and L[right] >= pivotkey:
            right -= 1
        L[left] = L[right]
    L[left] = pivotkey
    return left

def haha(a,k):
    def randSelect(a,k,left,right):
        #print("hao")
        if left==right:return

        p=pp(a,left,right)
        #print("---->",p,a)
        many=p-left+1
        #print("---->",many,k,p,a)
        if many==k:
            return
        elif many>k:
            randSelect(a,k,left,p-1)
        else:
            randSelect(a,k-many,p+1,right)
            #return randSelect(a,k-many,p+1,right)

    randSelect(a,k,0,len(a)-1)
    return a[:k]
k=22
a=[86, 899, 3, 242, 39,  535, 419, 974, 994, 441,  861, 154, 440, 437, 425, 226, 518, 869, 677, 501, 81,
   632, 70, 775, 843, 893, 601, 24, 839, 273, 849, 755, 539, 797]

from timeit import timeit

def h():
    haha(a,k)

t3 = timeit('h()', 'from __main__ import h', number=1)
print(t3)

#import random
#bbb=[random.randint(1,999) for i in range(322)]
#print(bbb)

三向切分快排，引用

class Quick3way():
    """三向切分的快速排序"""

    @classmethod
    def sort(cls, a):
        cls.sort_lh(a, 0, len(a) - 1)

    @classmethod
    def sort_lh(cls, a, lo, hi):
        if hi <= lo:
            return
        lt = lo
        i = lo + 1
        gt = hi
        v = a[lo]
        while i <= gt:
            if a[i] < v:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > v:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        # 结果a[lo..lt - 1] < v = a[lt..gt] < a[gt + 1..hi]
        cls.sort_lh(a, lo, lt - 1)
        cls.sort_lh(a, gt + 1, hi)

#版权声明：本文为CSDN博主「左岸小贼」的原创文章，遵循 CC 4.0 BY-SA 版权协议
#原文链接：https://blog.csdn.net/qdudz/article/details/51029341

对于三向切分，参见《算法》第四版，p189。