题目描述

给定一个无序数组 S = [s1,s2,…sk,…sn],输出数组的第 k 小元素，也就是从小到大，第 k 小元素。

分解

  • 如何将原数组分成两个子问题
    • 寻找一个中间元素
  • 如何找到这个处于中间位置的元素 m
    • 将 n 个元素分成 m 个组（通常每组 5 个元素），取每组的中间元素，再去这些中间元素的中间元素
  • 怎么找到中间元素的中间元素。
    • 递归调用

分为所有小于 m 数组 + 等于 m +大于 m 的所有数组