很早记得，出去面试，经常有人问：最大值怎么求，对一个经过变成训练的人，或许都会解这个题目，因为最大值是我们程序员的一个最最基本的素养。其实还可以拓展就最K大的值，也就是我们常说的top K问题，最大其实就是top 1大，还有第二大，第三大的问题吧。

其实对于K的问题，最简单的方式，就是先排序，排完序，孰大孰小，一目了然，这个是最基础的思路，不过本文会从其他更高效的路径出发，来解题。

最值求法

关于最大值求法，直接附伪代码：

1
2
3
4
5
6
7
8
9
10
int  max(arr) 
  if(arr == null) 
   throw expection


   max = arr[0]

   for(i = 1; i<arr.length ; i ++) 
       if(arr[i] > max)
             max = arr[i]

这个就是将最大值默认设置未第一个值，后面就和这个最大值比较，比这个最大值大的就直接替换掉，再和后面的值比较，直到最后，得到的最大值肯定是整个数组中最大的一个。

冒泡

冒泡排序其实就是这个思路，最大值（或者最小值）肯定在最后，次大在最大值（或者最小值）前面。

如对76，18，99，35， 12 进行排序：

冒泡一次，可将最小值求出，以此类推，第一次，需要76，18，99，35排序，次小值18就被冒泡出。

所以冒泡是可以解决top K的问题的，如求第二大的值，只需要进行K次冒泡即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// k表示第k大 k>=1
int  top_k_max(arr, k) 
  if(arr == null) 
   throw expection


  
  for(j = 0; j < k; j++)
    for(i = 0; i < arr.length -j ; i++)
       max = arr[0]
       if(arr[i] > arr[i+1]):
          exchange arr[i] with max // 相互交换

   return  arr[arr.length -k]
``` 

## 快排衍生

快排，绝对是高频词出现的排序算法，像java默认的数组排序就是排序的变种，那么top k咋还能跟快排有关系呢？我们就需要从快排的基本实现说起：

```java

  Quick-sort(Arr, p, r)
     // 分层两部分
     q  = Partition(Arr, p, r)
     // 比目标值大的
     Quick-sort(A, p, q-1)
     Quick-sort(A, q+1, r)


 Partition(Arr, p, r)
    // 将最右边的作为目标值
    x = Arr[r]

    i = p-1
    for（j = p to r-1）
        if(A[j] <= x)
            i = i +1
            exchange A[i] with A[j]
    exchange A[i+1] with x

我们假设是一个数据2,8,7,1,3.5,6,4

可以知道，第一轮排序

1
2 1 3 4 7 5 6 8

作为参考物的4 放到第4位，所以4肯定是第5大（7 5 6 8都比5大）的，因为前面的比它小（或相等），后面比它大（或相等）,这么一说你是不是有点思路啦。

你求K大，若是按照从小到大的顺序排序的话，肯定是在A.size - K位置上,需要转化下

其实快速排序将整个长数组，切成两部分，假设它所在的位置M，那他肯定是是第A.size-M大，如果这个A.size-M的值比K大，说明你要找的第k大是在比它大的那部分里面，再进行一次Partition，肯定还会有个中间数，在比较，知道你找到即可。
如刚才的2 1 3 4 7 5 6 8若是你求第6大，那么 A.size-M = 8-3 (4说在位置)< 6 ,所以去左边找，若是 A.size-M > k,去右边。

1
2
3
4
5
6
7
8
9
10
11
12
//若是求k大，从小到大排序应该是A.size-k 
Qsort-top-k(Arr, p, r, k)
     // 分层两部分
     q  = Partition(Arr, p, r)

     if(A.size-k  < q) 
        // 左边
        return Qsort-top-k(Arr, p, q-1, k)
     else if(A.size-k  >  q) 
         return  Qsort-top-k(Arr, q+1, r, k)
     else
         return Arr[q];