本文共 3528 字，大约阅读时间需要 11 分钟。

【题目描述】

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

【解题思路】：排序，再返回前 k 个元素

快速排序原理：

• 哨兵划分操作： 以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

• 递归： 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

下图为示例数组 [2,4,1,0,3,5] 的快速排序流程。

class Solution:    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:        def quick_sort(arr, l, r):            # 子数组长度为 1 时终止递归            if l >= r: return            # 哨兵划分操作（以 arr[l] 作为基准数）            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]            # 递归左（右）子数组执行哨兵划分            quick_sort(arr, l, i - 1)            quick_sort(arr, i + 1, r)                quick_sort(arr, 0, len(arr) - 1)        return arr[:k]'''作者：jyd链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/'''

复杂度分析：

• 时间复杂度 O(N * logN) ： 库函数、快排等排序算法的平均时间复杂度为O(N * logN) 。
• 空间复杂度 O(N) ： 快速排序的递归深度最好（平均）为 O(logN)

快排的两个写法

< 将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边 >

'''法1 左移右移完了再交换'''def quick_sort(arr, l, r):    print('最左端下标%d 最右端下标%d'%(l,r),end='\t')    print('基准arr[%d] = %d'%(l,arr[l]))    # 子数组长度为 1 时终止递归    if l >= r:         print('左下标 >= 右下标')        return    # 哨兵划分操作（以 arr[l] 作为基准数）    i, j = l, r    while i < j:        while i < j and arr[j] >= arr[l]:   # 从右向左 查找小于基准数的元素            j -= 1                          # 大于基准数 就继续左移            print('j-- 左移',j)        while i < j and arr[i] <= arr[l]:   # 从左向右 查找大于基准数的元素            i += 1                          # 小于基准数 就继续左移            print('i++ 右移',i)        arr[i], arr[j] = arr[j], arr[i]        print('交换:',i,j,arr)        print('==='*5)    arr[l], arr[i] = arr[i], arr[l]    print('arr[%d] = %d'%(l,arr[l]),end='\t')    print('arr[%d] = %d'%(i,arr[i]))    print('新arr:',arr)    print()        # 递归左（右）子数组执行哨兵划分    quick_sort(arr, l, i - 1)    print('=====左子数组排序完毕=====')    quick_sort(arr, i + 1, r)    print('================右子数组排序完毕================')    return arrarr = [2,4,1,0,3,5]print('Input:',arr)print('Output:',quick_sort(arr,0,len(arr)-1))

【快排2】

'''法2 左移交换+右移交换'''def QuickSort(array, left, right):    print('最左端下标%d 最右端下标%d'%(left,right))    if left >= right:        print('左下标 >= 右下标')        return array    pivot, i, j = array[left], left, right  # 初始化:i是最左端,j是最右端    t = 0    while i < j:        t+=1        # print('t =',t)        while i < j and array[j] >= pivot:  # 从右向左 查找小于基准数的元素            j -= 1                          # 大于基准数 就继续左移            print('j-- 左移',j)        array[i] = array[j]    # 小于基准数的元素 移动至其左边        print('base =',pivot,end=' ')        print('左下标%d 右下标%d'%(i,j),end=' ')        print('arr =',array)        while i < j and array[i] <= pivot:  # 从左向右 查找大于基准数的元素            i += 1                          # 小于基准数 就继续右移            print('i++ 右移',i)        array[j] = array[i]        print('base =',pivot,end=' ')        print('左下标%d 右下标%d'%(i,j),end=' ')        print('arr =',array)        print('==='*5)    array[j] = pivot    print('新arr:',arr)    print()    QuickSort(array, left, i-1)    print('=====左子数组排序完毕=====')    QuickSort(array, i+1, right)    print('================右子数组排序完毕================')        return arrayarr = [2,4,1,0,3,5]print('Input:',arr)print('Output:',QuickSort(arr,0,len(arr)-1))

转载地址：http://wbjii.baihongyu.com/