快排：
1、快速排序
2、快速排序寻找第K个大
3、最小的K个数
1、手写快排算法
class Solution:
def MySort(self , arr ):
# write code here
if not arr:
return
def q_sort(arr,left,right):
i=left
j=right
if i<j:
while i<j:
while i<j and arr[j]>=arr[left]:
j=j-1
while i<j and arr[i]<=arr[left]:
i=i+1
arr[i],arr[j]=arr[j],arr[i]
arr[left], arr[i] = arr[i], arr[left]
q_sort(arr,left,i-1)
q_sort(arr,i+1,right)
return arr
return q_sort(arr,0,len(arr)-1)
快排的核心算法可拆分为两步：
1）划分，把最左边的划分到正确的位置上
2）递归排序，左半部分和右半部分
2、寻找第K大的数
def findKth(self, a, n, K):
#划分找出来分界点
def partition(nums,left,right):
p=nums[left]
while left<right:
while left<right and nums[right]>=p:
right=right-1
nums[left]=nums[right]
while left<right and nums[left]<=p:
left=left+1
nums[right]=nums[left]
nums[left]=p
return left
def q_sort(nums,left,right,k):
if left<=right:
p=partition(nums,left,right)
if p== n-k:
return nums[p]
elif p < n-k:
#不断递归寻找划分点
return q_sort(nums,p+1,right,k)
else:
return q_sort(nums,left,p-1,k)
return q_sort(a,0,n-1,K)
3、最小的k个数基于快排：
核心代码如下：
if k >= len(arr): return arr
def quick_sort(l, r):
i, j = l, r
while i < j:
while i < j and arr[j] >= arr[l]: j -= 1
while i < j and arr[i] <= arr[l]: i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[l], arr[i] = arr[i], arr[l]
#不断递归排序
if k < i: return quick_sort(l, i - 1)
if k > i: return quick_sort(i + 1, r)
return arr[:k]
return quick_sort(0, len(arr) - 1)
