题目:N个无序的数（可能数目非常大），选出其中最大的K个数。这个题目有很多解法，最常用的是快速排序，部分排序，堆排序，计数排序，仅通过快速排序的改进来实现.
快速排序
快速排序平均的复杂度为O(NlogN)，核心代码如下:
<pre><code>` func quickSort(arr:inout [Int],low:Int,high:Int) {
if low >= high {
return
}
let mid:Int = partition(arr: &arr,low:low,high:high)
quickSort(arr: &arr, low: low, high: mid - 1)
quickSort(arr: &arr, low: mid + 1, high: high)
}
func partition(arr:inout [Int],low:Int,high:Int) -> Int {
let root:Int = arr[high]
var index:Int = low
for i in low...high {
if arr[i] > root {
if i != index {
swap(&arr[i], &arr[index])
}
index += 1
}
}
if index != high {
swap(&arr[high], &arr[index])
}
return index
}`</code></pre>
部分排序
题目要求只是寻找最大的K个数，我们将所有的元素都进行了排序，其实只要将最大的K个数排好序就好了，没必要将剩下的N-K个数也进行排序。
可以复用快速排序来完成这个部分排序的功能，在快速排序中，每一轮都需要选定一个pivot，每一轮排序完成后，比pivot大的数都排在它前（后）面，而比pivot小的数都排在它的后（前）面。假设前面的序列为a，后面的序列为b，a的长度为n.
当n>K时，我们直接输出a的前K个元素就好了；
当n=K时，我们直接输出a这个序列；
当n<K时，我们就需要从b中找出K−n个元素和a一起输出就好了。
<pre><code>` func kBigNumber(arr:inout [Int],low:Int,high:Int,k:Int)->Int {
var result:Int = -1
if low <= high {
let index = partition(arr: &arr, low: low, high: high)
let num:Int = index - low + 1 // index 之前数组暂定为a, index 之后的数组定为b
if num > k { // 如果a的数据大于b的要求，从a 中选择k个数字
result = kBigNumber(arr: &arr, low: low, high: index - 1, k: k)
} else if num < k { //如果a的个数不够的话，那么再从b中找K-n个
result = kBigNumber(arr: &arr, low: index + 1, high: high , k: k - num)
} else {
result = index
}
}
return result
}`</code></pre>
测试代码:
<pre><code>var kData:[Int] = [1,2,3,4,8,3,2,5,10,100,30] var bigIndex:Int = -1 bigIndex = bigNumber.kBigNumber(arr: &kData, low: 0, high: kData.count - 1, k: 4) if bigIndex >= 0 { for i in 0...bigIndex { print("FlyElephant---最大的k个数---\(kData[i])") } print("FlyElephant--部分排序之后的数据---\(kData)") }</code></pre>
