三路快排算法-求中位数问题(4)

算法面试高频题，求前K个数，或者求中位数

引至51CTO

三路快排算法思路

1. 将数组分为三部分，随机选择数组中的一个数，使数组左边都小于这个数，右边大于这个数。
2. 在递归处理左边数组，右边数组。

step1排列数组的时间复杂度是O(N)，空间复杂度是O(1)
step2 递归调用的复杂度O(logN)

总体的时间赋值度O(NlogN)

Step 1 算法解释

    def __QuickSort(self,a,l,r):
        #a[l,r)
        if(l+1>=r):
            return
        rand_index = random.randint(l,r-1) 
        self.swap(a,l,rand_index) ## 对已经排好序的数组，有优化作用
        gt = r ##右边的指针位置
        lt = l ##左边的指针位置
        i = l+1 ## 遍历指针
        while(i<gt): ##遍历条件
            if(a[i]>a[l]):
                self.swap(a,i,gt-1)
                gt = gt -1 ##将大数换到右端，大数指针--
            elif(a[i]<a[l]):
                self.swap(a,lt+1,i)
                i = i+1
                lt= lt+1 ## 将小数换到左端，小数指针--
            else:
                i = i+1 ## 相等的数据，步进指针++
        self.swap(a,l,lt) ##将小数的最后一个和第一个数交换，结果是[l,lt)是小数
        self.__QuickSort(a,gt,r)
        self.__QuickSort(a,l,lt) ##递归调用

求中位数算法

利用快速排序思想，只处理中位数所在的区域（中数、大数或小数）

• 中位数在大数区，对大数区快速排序
• 中位数在小数区，对小数区快速排序
• 中位数在中数区，返回

考虑中位数是len//2，len//2-1情况

def __swap(a,i,j):
    tmp  = a[i]
    a[i] = a[j]
    a[j] = tmp
    
def insertSort(a,l,r):
    #a[l,r)
    i = l
    while(i<r):
        j = i
        while(j>l):
            if (a[j]<a[j-1]):
                __swap(a,j,j-1)                
            else:
                break 
            j = j-1
        i = i+1

def sortMid(a):
    mid = len(a)//2
    sortHead(a,mid)
    
def sortHead(a,k):
    #a[l,r)
    assert(k<len(a))
    __sortHead(a,0,len(a),k)

def __sortHead(a,l,r,k):
    if(r-l<10):
        insertSort(a,l,r)
        return    
    rand = random.randint(l,r-1)
    __swap(a,l,rand)
    
    lt = l
    gt = r
    i  = l
    while(i<gt):
        if(a[i]>a[l]):
            __swap(a,gt-1,i)
            gt = gt -1
        elif(a[i]<a[l]):
            __swap(a,lt+1,i)
            i= i +1
            lt = lt + 1
        else:
            i = i+1
    __swap(a,lt,l)
## 判断k在哪个区域
    if(k-1<lt):
        ## 将k-1也进行排序，考虑len//2-1
        __sortHead(a,l,lt,k)
    if(k>=gt):
        __sortHead(a,gt,r,k)

测试代码

import copy
for i in range(50):
    total = random.randint(0,200000)
    a = np.random.randint(0,total,500000)
    a.tolist()
    b =  copy.copy(a)
    a.sort()
    mid1 = a[len(a)//2]
    mid1_left = a[len(a)//2-1]
    sortMid(b)
    mid2 = b[len(a)//2]
    mid2_left = b[len(a)//2-1]
    if(mid1 == mid2 and mid1_left==mid2_left):
        print("True")
    else:
        print("Flase")