通用基础-排序算法

快速排序

首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序

最好情况：每次划分过程产生的区间大小都为n/2，一共需要划分log₂n次，每次需要比较n-1次，O(nlog₂n)
最坏情况：每次划分过程产生的两个区间分别包含n-1个元素和1个元素，一共需要划分n-1次，每次最多交换n-1次，这就是冒泡排序了，O(n2)

堆排序

1. 根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
2. 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

堆排序过程的最好和最坏时间复杂度是O(nlog₂n)

TOP K

如何在N个元素中寻找前K大的数？

快速排序：

• 原理：每次快速排序中的划分过程能找到一个全部大于左边元素的一个值。如果该值的位置等于K，那么这个值和它左边的所有元素就是前K大的数；如果该值的位置小于K，那么对右边的元素继续划分排序；如果该值的位置大于K，那么对左边的元素继续划分排序
• 问题：但空间复杂度是O(N)，如果你要在很多元素中找很少几个top K的元素，或者在一个巨大的数据流里找到top K，快速排序是不合适的，堆排序更省地方

堆排序：

• 原理：申请一个容量为K的数组，存入数组的前K个元素，创建长度为K的最小堆；从K开始循环数组的剩余元素，如果元素(a)比最小堆的根节点大，将a设置成最小堆的根节点，然后重建最小堆；循环完成后，最小堆中的所有元素就是需要找的最大的K个元素。
• 优点：可以在N个元素中找到top K，时间复杂度是O(N log K)，空间复杂的是O(K)