资料

基于快排的快速选择算法

快速排序亲兄弟：快速选择算法

快速选择-维基百科，自由的百科全书

解读

• 快速选择其实是快排的变种，快排的思想就是以pivot为枢轴，交换两边的数字，交换完毕的最终效果是pivot左边都小于等于pivot，右边都大于pivot。设pivot的下标为p，则说明找到了数组中第p大元素。
• 若要寻找第k大的元素，若k大于p，则k一定在大于p的区域；若k小于p，则k一定在小于p的区域。再继续递归寻找即可。
• 设数组大小为n。如果要寻找中位数，那就是要找第int(n/2)大的数。
• 这种方法最大的好处就是可以达到O(n)的时间复杂度。

时间复杂度分析

• 最好

  设每次pivot正好是从小到大正中间的数，则需要遍历N+N/2+N/4+N/8+...+1 = 2N个元素

  时间复杂度O(N)

• 最差

  设每次pivot是第从小到大一个数，则需要遍历N + N-1 + N-2 + ... + 1 = N^2个元素。类似于快排的平衡树退化为链表。

  时间复杂度O(N^2)

不过维基上说可以通过选择pivot的技巧来做到最坏情形下依然保证O(N)的时间复杂度。

问题

有点晕，到底是找第K大的元素还是在第K个位置的元素？---第K个位置！因此可以用来找中位数

这个结论的由来：在215. 数组中的第K个最大元素中使用可通过题解进行测试，[1,2,3,4,5,5,5] 2的答案是5而非4