06-20：刷题综合三：快排

快排：

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)