快排思路

快速排序算法的思路是找到一个基准值(一般是数组的第一个元素），使得比基准值小的元素放在基准值的左边，比基准值大的元素放在基准值的右边。

快排的递归实现

leetcode原题练手地址
数组中最小的k个数
参照以上思路的python代码如下，需要注意的是在每次递归调用Qsort的时候需要考虑arr为空的情况，否则arr[0]会越界:

  def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
       # 排序 递归实现
        def Qsort(arr):
            if not len(arr):
                 return []
            else:
                tmp=arr[0]
                large=[item for item in arr if item>tmp]
                equ=[item for item in arr if item==tmp]
                small=[item for item in arr if item<tmp]
                return Qsort(small)+equ+Qsort(large)
        arr=Qsort(arr)
        return arr[:k]

快排的非递归实现

递归的思想是对每次确定位置的arr，排序其左边比其小的数组，右边比其大的数组，所以需要确定排序的左右边界，所以非递归的方法需要用一个栈来保存每次调用的左右边界，代码示意如下：

 #排序 非递归实现 
        def Qsort(arr):
            if len(arr)<2:
                return arr
            stack=[len(arr)-1,0]
            while stack:
                l=stack.pop()
                r=stack.pop()
                ind=partition(arr,l,r)
                if l<ind-1:
                    stack.append(ind-1)
                    stack.append(l)
                if r>ind+1:
                    stack.append(r)
                    stack.append(ind+1)
        def partition(arr,left,right):
            tmp=arr[left]
            while left<right:
               #从后往前找比基准值小的
                while left<right and arr[right]>=tmp:
                    right-=1
               #赋值给left
                arr[left]=arr[right]
               #从前往后找比基准值大的
                while left<right and arr[left]<=tmp:
                    left+=1
                #赋值给right
                arr[right]=arr[left]
            #最终位置的 赋值
            arr[left]=tmp
            return left
        Qsort(arr)
        return arr[:k]