十万个无序数字怎么快速排序

Question

另一个问题：十万个无序数字怎么平均分成两堆，保证前一堆的每个数字都比后一堆怎么排快一点，随机选基准然后快排吗

Answer 1

• 思路：找出大小为n的数组vec的中位数，以中位数为基准对数组进行划分。

• 时间复杂度：O(n)。

• 空间复杂度：O(1)。

• 具体步骤

• 以中位数为基准进行划分。
  当n为偶数，中位数在第n/2大的数和第(n/2)+1大的数中。因为是划分成相等的两堆，以第n/2大的数为基准划分即可，大的划分到右边，其余划分到左边。（当n为奇数，同理可推，就不再论述）

• 寻找中位数。
  从上面可看出，寻找中位数即寻找数组中第K大的数。而寻找数组中第K大的数的算法有很多，而一种时间复杂度为O(n)且空间复杂度为O(1)的算法则是：类似于快排对数组进行划分，但与快排不同的是：因为寻找的是第K大的数，第K大的数只会在其中一组，所以只对第K大的数的那一组进行递归划分。时间复杂度是O(n)。算法的具体细节可见相关博客，搜索下关键词“寻找 第k大 数”就看见有很多博客具体分析了这个算法。

• 实质上以类快排方式划分的过程中，就已经把大于中位数的数划分到数组右边，其余划分到数组左边了。找到中位数的时候，也就是划分完成了。