求数组中的第K大元素

diggersun

给定一个数组，求其中第K大的元素。

若K=1，是求最大的元素，一般的做法是假设A0最大，然后从A1到 An逐个和他比较，大的留下来，最后留下来的就是最大的元素，我称之为打擂台方式。


若K=2，是求次大的元素，一般的做法是先比较A0和A1，求出最大次大，然后从A2到 An逐个和他们比较，有三种情况，对应三种决策，比最大的大，介于最大和次大之间，比次大的还小。这样也是一种打擂台方式。只是留在台上的是两个人而不是一个。


若K比较大呢？有的同学想现将数组排序，然后直接输出第K大，这样做很是浪费，一个改进的做法是选择排序选择到第K次的时候，或者冒泡排序冒到第K次的时候就不再继续了。


以选择排序为例，第一轮选择实际上将当前最小（大）的数字和数组的第一个数字进行交换，那么，等到第K个数字完成交换后，其实第K小（大）已经求出，无需基础排完整个数组。

有一种分治的思想很重要，可以用来解决这一类的问题，我们这里详细说说：
1、将数组的首元素作为划分元素X，从数组后面开始，每次找到一个比X小的数字，我们把它和X换，相当于换到了前面，然后从前面找到比X大的数字，和X交换，相当于往后面换，直到指针交错无法交换为止，这样，一轮交换后，X到了某个位置，它前面数字都比它小，后面的数字都比它大。
2、假设X的位置Y刚好是第K，那么问题解决了，若Y>k，说明要到前面找，若Y<K，说明要到前面去找，直到Y==k

这样做的话，对于K比较大是很有利的，因为每次几乎都是减半，快于每次减1。前面选择排序或者冒泡，下次查找只比上一次少了一个元素，减少的有限。

diggersun

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int a[20]= {10,1,7,3,5,9,8,2,6,4,11,13,25,19,17,20,12,18,16,15};
   
5. int partion(int *a,int l,int r)
   
6. {
   
7.     int p=a[l];//划分元素定为A[l]
   
8.     while(l<r)
   
9.     {
   
10.         while((a[r]>=p)&&(l<r))r--;//后面找比P小的数
    
11.         a[l]=a[r];
    
12.         while((a[l]<=p)&&(l<r))l++;//前面找比P大的数
    
13.         a[r]=a[l];
    
14.     }
    
15.     a[l]=p;return l;
    
16. }
    
17. 
    
18. int main()
    
19. {
    
20.     int x=8;//其实是求第8小，最小的是第0小
    
21.     int l=0,r=19;
    
22.     bool bb=true;
    
23.     int t;
    
24.     do
    
25.     {
    
26.         t=partion(a,l,r);// 得到划分元素的位置
    
27.         if (t>x)r=t-1;  //若位置比x大，说明第X小的在前面
    
28.         else if (t<x)l=t+1;//到后面去找
    
29.         else bb=false;//相等表示找到了
    
30.     } while (bb);
    
31.     cout<<a[x]<<endl;
    
32.     return 0;
    
33. }
    

复制代码

admin

1. #include <iostream>
   
2. using namespace std;
   
3. const int mm=10;
   
4. int a[mm];
   
5. int i;
   
6. int hf(int l,int r)
   
7. {
   
8.     int p=a[l];
   
9.     while (l<r)
   
10.     {
    
11.         while ((a[r]>=p) &&(l<r) ) r--;  ///一定是先从右边找小的
    
12.         a[l]=a[r];
    
13.         while ((a[l]<=p) &&(l<r) ) l++;  ///再从左边找大的
    
14.         a[r]=a[l];
    
15.     }
    
16.     a[l]=p;
    
17.     return l;
    
18. }
    
19. 
    
20. int get(int x,int l,int r)
    
21. {
    
22.     int p=hf(l,r);
    
23.     if (p==x) return a[x];
    
24.     else if (p>x) return  get(x,l,p-1);
    
25.     else return get(x,p+1,r);
    
26. }
    
27. 
    
28. int main()
    
29. {
    
30.     ///在很顺序的里面找
    
31.     for (i=0; i<=9; i++) a[i]=i;
    
32.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';
    
33. 
    
34.     cout<<endl;
    
35.     ///在倒序中找
    
36.     for (i=0; i<=9; i++) a[i]=9-i;
    
37.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';
    
38. 
    
39.     cout<<endl;
    
40.     ///在相同的中找
    
41.     for (i=0; i<=9; i++) a[i]=1;
    
42.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';
    
43. 
    
44.     ///在部分相同的中找
    
45.     cout<<endl;
    
46.     for (i=0; i<=9; i++) a[i]=10-i%2;
    
47.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';
    
48. 
    
49.     ///在乱序的中找
    
50.     cout<<endl;
    
51.     for (i=0; i<=9; i++) a[i]=i*i%10;
    
52.     for (i=0; i<=9; i++) cout<<get(i,0,9)<<' ';
    
53.     ///请体会此中的测试技巧
    
54.     return 0;
    
55. }
    

复制代码

admin

二楼的是以前对我校高中生讲的，写的是非递归的，很精妙，三楼的是递归的，很容易想到，建议初学者先学三楼的做法。