Quick Select Algorithm 快速选择算法

(108) 2024-04-21 07:01:01

更多代码和Leetcode题目解析请看这里

什么是Quick select?

  • Quick select算法通常用来在未排序的数组中寻找第k小/第k大的元素。其方法类似于Quick sortQuick selectQuick sort都是由Tony Hoare发明的,因此Quick select算法也被称为是Hoare's selection algorithm
  • Quick select算法因其高效和良好的average case时间复杂度而被广为应用。Quick select的average case时间复杂度为O(n),然而其worst case时间复杂度为O(n^2)
  • 总体而言,Quick select采用和Quick sort类似的步骤。首先选定一个pivot,然后根据每个数字与该pivot的大小关系将整个数组分为两部分。那么与Quick sort不同的是,Quick select只考虑所寻找的目标所在的那一部分子数组,而非像Quick sort一样分别再对两边进行分割。正是因为如此,Quick select将平均时间复杂度从O(nlogn)降到了O(n)

Quick select算法描述

Input: array nums, int k. (find kth smallest element in an unsorted array)
Output: int target

  1. Choose an element from the array as pivot, exchange the position of pivot and number at the end of the array.
    • The
THE END

发表回复