- 此篇博文主要是对面试过程中的算法题进行记录。
- 该题作为面试常见题型，同时拥有多种实现方式。
- 后续会对相关算法进行具体代码实现。
题目描述：
有很多个无序的数，怎么选出其中最大的若干个数？即，从n个数中选出最大的K个数。
解法一:
元素数量不多的情况下，使用对应的排序算法来对数据进行排序，再输出最大的前K个数。
两种排序（部分排序，全部排序）
全部排序：( 时间复杂度均为O(Nlog2N) )
快速排序：
- 选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
堆排序：
- 创建大顶堆或小顶堆，然后将第一个和最后一个节点进行交换，输出最后一个节点，再调整堆
存在的问题：
- 即便是K=1的情况，上面的算法复杂度仍然是O(Nlog2N)，而显然，我们可以通过n-1此的比较和交换得到结果，不需要对整个数组进行排序。
- 要避免做后面N-K个数的排序，可以使用部分排序算法，
部分排序：把n个数中的前K个数排序出来，复杂度是O(N*K)。
选择排序：
- 假设第一个是最小的数，遍历该数之后的数比较大小，若更小，则min指向该数，循环遍历下来之后每一次都能找到未排序数组中的最小值。
冒泡排序：
- 每次比较相邻的两个数，根据大小关系进行交换。一趟下来，最大值位于最后
结论:
- 哪一个更好呢？O(nlog2n) 和O(n*K)？这取决于K的大小，在K<log2n的情况下，可以选择部分排序。
解法二
利用快速排序的思想
快排回顾：
- 快排中的每一步，都是将数据分为两组，其中一组的任何数都小于另一组中的任何数，不断地对数据进行分割直到不能再分即完成排序。
解决方案：
- 假设n个数存储在数组S中，从S中找出一个元素X，它把数组分为比它大的和比它小的两部分，假设比它大的一部分数组是Smax，比它小的部分是Smin。
- 此时两种情况：
- Smax中元素不足K个，说明Smax中的所有数和Smin中最大的K-|Smax|个元素就是数组S中最大的K个数；对于Smin则递归进行对应的操作。
- Smax中元素的个数大于或等于K，则需要返回Smax中最大的K个元素。
结论：
- 递归下去，问题的规模不断地变小，平均时间复杂度O(n * log2K)。
解法三（部分堆排序实现）
前两个解法都存在统一的问题，需要对数据访问多次，只能适用于数据量较小的情况。若数据量较大，则不能全部装入内存，所以要求尽可能少地遍历数据。
- 最好的情况就是K个数，则该K个数则为最大的K个数。如果有K+1个数，则需要比较原K个数中最小的数min和后新加入的一个数temp。若temp>min，则temp替换min。
- 对于第K+2和K+3个数则与之同理。
步骤概括：所耗费的时间复杂度为O(n * K)。
- 判断前一步是否有交换？
- 若有寻找出K个值中最小的值，若无保持上一次的最小值
- 比较要新加入的值和选出的最小值
- 若temp>min,则替换对应的min，否则保持
对于寻找最小值以及替换的问题
- 可以利用堆排序来实现
堆排序实现：
- 可以使用容量为K的最小堆来存储最大的K个数、最小堆的堆顶就是最小值，考虑加入新的元素时，则只需要比较堆顶和新加入的元素的大小，来对应的进行堆顶的替换。与此同时进行堆结构的调整。保证最小堆的性质。更新过程花费的时间复杂度为O(log2K)。
- 此时的时间复杂度则为O(n * log2K)
