体会编程之美，找出最大的k个数

 今日上课无事,偶尔看到《编程之美》的一道题目，如何找出n个数中的最大的k个数，不仅惊奇于其提供的多种解法，而且感叹其中很多解法都是之前的我们熟悉解法的变种。废话不多说，我们来依次看一下不同的解法和相应的分析

思路一

1. 使用排序算法先对n个数进行排序，然后取最大的k个数。
2. 先找出n个数中最大值，然后在找出n-1个数中的最大值，一直进行，知道找出k个数。

 我们来分析一下两种方法的效率，如果使用快排进行排序，那么时间复杂度就是O(nlog2n),而第二个方法的时间复杂度为O(kn),所以二者的效率高低取决于k相对于log2n的大小，如果k>log2n,那么使用第一种方法比较好，反之，便是使用第二种方法比较好。

思路二

 使用顺序统计量的思路：在一个有n个元素组成的集合中，第i个顺序统计数就是该集合中第i小的元素。对《算法导论》中利用快排查找n个数中中位数的算法进行修改。
在本问题中，假设N个数存储在数组S中，我们从数组S中随机找出一个元素X，从而把数组分为Sa和Sb，Sa中的元素都大于等于X,Sb中的元素都是小于X
  这个时候有
  1 .Sa中的元素个数小于k，Sa中的所有的数和Sb中的最大的k-|Sa|个元素为数组S中最大的k个数
  2 .Sa中的元素大于或者等于k，则需返回Sa中的最大的k个元素。
 这也是二分法思想的体现。

思路三

 使用动态编程的思想，并且解决上述解法中都要多次读取n个数的问题，当n大到一定程度之后，这样会很耗费时间。
主要思想就是维持一个规模为k的数据结构，存储最大的k个值，然后依次遍历n个数，如果发现比数据结构中数小的值，就对数据结构进行更新，遍历结束之后，数据结构中就是n个数中的最大的n个数
 如果使用数组来表示数据结构，那么时间复杂度就是O(kn),但如果使用最小堆来表示，那么时间复杂读就是O(nlog2k)。

思路四

 上述的思路都是基于n个数相互比较的解法，如同《算法导论》中的想法，我们可以使用其他方式的比较来获得n个数的大小关系。所以，如果n个数都是在一个整数范围之内，我们可以修改计数排序和基数排序来找出最大的k个数。