算法面试高频题，求前K个数，或者求中位数
引至51CTO
三路快排算法思路
- 将数组分为三部分，随机选择数组中的一个数，使数组左边都小于这个数，右边大于这个数。
- 在递归处理左边数组，右边数组。
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")
