【分治法】线性时间选择（转）

转自：http://blog.csdn.net/liufeng_king/article/details/8480430

线性时间选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，（这里给定的线性集是无序的）。

1、随机划分线性选择

线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分，与快速排序不同的是，它只对划分出的子数组之一进行递归处理。

程序清单如下：

 1 //2d9-1 随机划分线性时间选择  
 2 #include "stdafx.h"  
 3 #include <iostream>   
 4 #include <ctime>  
 5 using namespace std;   
 6   
 7 int a[] = {5,7,3,4,8,6,9,1,2};  
 8   
 9 template <class Type>  
10 void Swap(Type &x,Type &y);  
11   
12 inline int Random(int x, int y);  
13   
14 template <class Type>  
15 int Partition(Type a[],int p,int r);  
16   
17 template<class Type>  
18 int RandomizedPartition(Type a[],int p,int r);  
19   
20 template <class Type>  
21 Type RandomizedSelect(Type a[],int p,int r,int k);  
22   
23 int main()  
24 {  
25     for(int i=0; i<9; i++)  
26     {  
27         cout<<a[i]<<" ";  
28     }  
29     cout<<endl;  
30     cout<<RandomizedSelect(a,0,8,3)<<endl;  
31 }  
32   
33 template <class Type>  
34 void Swap(Type &x,Type &y)  
35 {  
36     Type temp = x;  
37     x = y;  
38     y = temp;  
39 }  
40   
41 inline int Random(int x, int y)  
42 {  
43      srand((unsigned)time(0));  
44      int ran_num = rand() % (y - x) + x;  
45      return ran_num;  
46 }  
47   
48 template <class Type>  
49 int Partition(Type a[],int p,int r)  
50 {  
51     int i = p,j = r + 1;  
52     Type x = a[p];  
53   
54     while(true)  
55     {  
56         while(a[++i]<x && i<r);  
57         while(a[--j]>x);  
58         if(i>=j)  
59         {  
60             break;  
61         }  
62         Swap(a[i],a[j]);  
63     }  
64     a[p] = a[j];  
65     a[j] = x;  
66     return j;  
67 }  
68   
69 template<class Type>  
70 int RandomizedPartition(Type a[],int p,int r)  
71 {  
72     int i = Random(p,r);  
73     Swap(a[i],a[p]);  
74     return Partition(a,p,r);  
75 }  
76   
77 template <class Type>  
78 Type RandomizedSelect(Type a[],int p,int r,int k)  
79 {  
80     if(p == r)  
81     {  
82         return a[p];  
83     }  
84     int i = RandomizedPartition(a,p,r);  
85     int j = i - p + 1;  
86     if(k <= j)  
87     {  
88         return RandomizedSelect(a,p,i,k);  
89     }  
90     else  
91     {  
92         //由于已知道子数组a[p:i]中的元素均小于要找的第k小元素  
93         //因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。  
94         return RandomizedSelect(a,i+1,r,k-j);  
95     }  
96 }

View Code

程序解释：利用随机函数产生划分基准，将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r]，使a[p:i]中的每个元素都不大于a[i+1:r]中的每个元素。接着"j=i-p+1"计算a[p:i]中元素个数j.如果k<=j，则a[p:r]中第k小元素在子数组a[p:i]中，如果k>j，则第k小元素在子数组a[i+1:r]中。注意：由于已知道子数组a[p:i]中的元素均小于要找的第k小元素，因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。

在最坏的情况下，例如：总是找到最小元素时，总是在最大元素处划分，这是时间复杂度为O(n^2)。但平均时间复杂度与n呈线性关系，为O(n)(数学证明过程略过,可参考王云鹏论文《线性时间选择算法时间复杂度深入研究》)。

2、利用中位数线性时间选择

中位数：是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据。

算法思路：如果能在线性时间内找到一个划分基准使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1),那么就可以在最坏情况下用O(n)时间完成选择任务。例如，当ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递推式T(n)<=T(9n/10)+O(n)。由此可得T(n)=O(n)。

实现步骤：

(1)将所有的数n个以每5个划分为一组共组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。将每组中的元素排好序再分别取每组的中位数，得到个中位数。

(2)取这个中位数的中位数，如果是偶数，就找它的2个中位数中较大的一个作为划分基准。

(3)将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。在这种情况下找出的基准x至少比个元素大。因为在每一组中有2个元素小于本组的中位数，有个小于基准，中位数处于，即个中位数中又有个小于基准x。因此至少有个元素小于基准x。同理基准x也至少比个元素小。而当n≥75时≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

程序清单如下：

  1 //2d9-2 中位数线性时间选择  
  2 #include "stdafx.h"  
  3 #include <ctime>  
  4 #include <iostream>   
  5 using namespace std;   
  6   
  7 template <class Type>  
  8 void Swap(Type &x,Type &y);  
  9   
 10 inline int Random(int x, int y);  
 11   
 12 template <class Type>  
 13 void BubbleSort(Type a[],int p,int r);  
 14   
 15 template <class Type>  
 16 int Partition(Type a[],int p,int r,Type x);  
 17   
 18 template <class Type>  
 19 Type Select(Type a[],int p,int r,int k);  
 20   
 21 int main()  
 22 {  
 23     //初始化数组  
 24     int a[100];  
 25   
 26     //必须放在循环体外面  
 27     srand((unsigned)time(0));  
 28   
 29     for(int i=0; i<100; i++)  
 30     {  
 31         a[i] = Random(0,500);  
 32         cout<<"a["<<i<<"]:"<<a[i]<<" ";  
 33     }  
 34     cout<<endl;  
 35   
 36     cout<<"第83小元素是"<<Select(a,0,99,83)<<endl;  
 37   
 38     //重新排序，对比结果  
 39     BubbleSort(a,0,99);  
 40   
 41     for(int i=0; i<100; i++)  
 42     {  
 43         cout<<"a["<<i<<"]:"<<a[i]<<" ";  
 44     }  
 45     cout<<endl;  
 46 }  
 47   
 48 template <class Type>  
 49 void Swap(Type &x,Type &y)  
 50 {  
 51     Type temp = x;  
 52     x = y;  
 53     y = temp;  
 54 }  
 55   
 56 inline int Random(int x, int y)  
 57 {  
 58      int ran_num = rand() % (y - x) + x;  
 59      return ran_num;  
 60 }  
 61   
 62 //冒泡排序  
 63 template <class Type>  
 64 void BubbleSort(Type a[],int p,int r)  
 65 {  
 66      //记录一次遍历中是否有元素的交换     
 67      bool exchange;    
 68      for(int i=p; i<=r-1;i++)    
 69      {    
 70         exchange = false ;    
 71         for(int j=i+1; j<=r; j++)    
 72         {    
 73             if(a[j]<a[j-1])    
 74             {    
 75                 Swap(a[j],a[j-1]);   
 76                 exchange = true;    
 77             }     
 78         }     
 79         //如果这次遍历没有元素的交换,那么排序结束     
 80         if(false == exchange)    
 81         {  
 82              break ;    
 83         }  
 84      }  
 85 }  
 86   
 87 template <class Type>  
 88 int Partition(Type a[],int p,int r,Type x)  
 89 {  
 90     int i = p-1,j = r + 1;  
 91   
 92     while(true)  
 93     {  
 94         while(a[++i]<x && i<r);  
 95         while(a[--j]>x);  
 96         if(i>=j)  
 97         {  
 98             break;  
 99         }  
100         Swap(a[i],a[j]);  
101     }     
102     return j;  
103 }  
104   
105   
106 template <class Type>  
107 Type Select(Type a[],int p,int r,int k)  
108 {  
109     if(r-p<75)  
110     {  
111         BubbleSort(a,p,r);  
112         return a[p+k-1];  
113     }  
114     //(r-p-4)/5相当于n-5  
115     for(int i=0; i<=(r-p-4)/5; i++)  
116     {  
117         //将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置  
118         //使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数  
119         BubbleSort(a,p+5*i,p+5*i+4);  
120         Swap(a[p+5*i+2],a[p+i]);  
121     }  
122     //找中位数的中位数  
123     Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);  
124     int i = Partition(a,p,r,x);  
125     int j = i-p+1;  
126     if(k<=j)  
127     {  
128         return Select(a,p,i,k);  
129     }  
130     else  
131     {  
132         return Select(a,i+1,r,k-j);  
133     }  
134 }

View Code

运行结果如下：