C++分治策略實作線性時間選擇

問題描述：

給定線性序集中n個元素和一個整數k，1≤k≤n，要求找出這n個元素中第k小的元素，即如果將這n個元素依其線性序排列時，排在第k個的元素即為要找到元素，

細節須知：（與之前的隨筆相比）

（1）設定了對于程式運行次數的手動輸入設定

（2）取消了檔案的讀入，直接生成亂數進行排序查找

（3）擴大了亂數的范圍、陣列的可申請大小

（4）時間統計精確到了微秒級

（5）運行結束后一次性寫入提升了程式穩定性，寫入的資料可用于資料分析圖表

演算法原理：

將n個輸入元素劃分成?n/5?個組，每組5個元素，只可能有一個組不是5個元素，用任意一種排序演算法，將每組中的元素排好序，并取出每組的中位數，共?n/5?個，遞回呼叫演算法Select來找出?n/5?個元素的中位數，如果?n/5?是偶數，就找它的兩個中位數中較大的一個，以這個元素作為劃分基準，以此遞回排序找到所需的第k項，

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<fstream>
  6 #include<algorithm>
  7 #include<windows.h>
  8 #include<ctime>
  9 using namespace std;
 10 LARGE_INTEGER nFreq;//LARGE_INTEGER在64位系統中是LONGLONG，在32位系統中是高低兩個32位的LONG，在windows.h中通過預編譯宏作定義
 11 LARGE_INTEGER nBeginTime;//記錄開始時的計數器的值
 12 LARGE_INTEGER nEndTime;//記錄停止時的計數器的值
 13 
 14 //一次快排
 15 int Partition(int nums[],int p,int r,int x)
 16 {
 17     if(p>r) return -1;
 18     //找出基準x的位置并與第一位交換
 19     for(int i=p;i<=r;i++)
 20     {
 21         if(nums[i]==x)
 22         {
 23             swap(x,nums[p]);
 24             break;
 25         }
 26     }
 27     int left=p,right=r;
 28     while(left<right)
 29     {
 30         while(left<right && nums[right]>=x) right--;
 31         nums[left]=nums[right];
 32         while(left<right && nums[left]<x) left++;
 33         nums[right]=nums[left];
 34     }
 35     nums[left]=x;
 36     return left;
 37 }
 38 
 39 //快速排序
 40 void QuickSort(int nums[],int low,int high)
 41 {
 42     if(low>high) return;
 43     int key=nums[low];
 44     int left=low,right=high;
 45     while(left<right)
 46     {
 47         while(left<right && nums[right]>=key) right--;
 48         nums[left]=nums[right];
 49         while(left<right && nums[left]<key) left++;
 50         nums[right]=nums[left];
 51     }
 52     nums[left]=key;
 53     QuickSort(nums,low,left-1);
 54     QuickSort(nums,left+1,high);
 55 }
 56 
 57 int Select(int nums[],int p,int r,int k)
 58 {
 59     if(r-p<75)
 60     {
 61         QuickSort(nums,p,r);
 62         return nums[p+k-1];
 63     }
 64     //每5個為一組，找到各組的中位數，并存盤在前(r-p-4)/5個位置里
 65     for(int i=0;i<=(r-p-4)/5;i++)
 66     {
 67         QuickSort(nums,p+5*i,p+5*i+4);
 68         swap(nums[p+i],nums[p+5*i+2]);
 69     }
 70     //找所有中位數的中位數
 71     int x=Select(nums,p,p+(r-p-4)/5,(r-p-4)/10);
 72     //以x為基準做一次快排
 73     int i=Partition(nums,p,r,x);
 74     int j=i-p+1;
 75     //判斷k屬于那個部分
 76     if(k<=j)
 77         return Select(nums,p,i,k);
 78     else
 79         return Select(nums,i+1,r,k-j);
 80 }
 81 int main(){
 82     ofstream fout;
 83     double cost;
 84     int i = 0,m = 0,n = 0,key = 0;
 85     cout<<"Please enter the number of times you want to run the program:";        //輸入程式運行次數
 86     cin>>m;
 87     int data_amount[m];
 88     double runtime[m];
 89     srand((unsigned int)time(NULL));      //設定亂數種子
 90     for(i=0;i<m;i++)
 91     {
 92         n=10000+RAND_MAX*(rand()%300)+rand();           //RAND_MAX=32767,隨機生成資料量
 93         data_amount[i]=n;                               //限定資料規模為10000~9872867
 94         cout<<"☆The "<<i+1<<"th test Data amount is："<<n<<endl;
 95         int j=0;
 96         int *a=(int *)malloc(n*sizeof(int));
 97         for(j=0;j<n;j++){
 98             a[j]=RAND_MAX*(rand()%400)+rand();          //隨機生成0~13139567的亂數
 99         }
100         key=rand()%10000+1;   //隨機生成1~10000作為所要選擇的次序
101         QueryPerformanceFrequency(&nFreq);//獲取系統時鐘頻率
102         QueryPerformanceCounter(&nBeginTime);//獲取開始時刻計數值
103         int t=Select(a,0,n-1,key);
104         QueryPerformanceCounter(&nEndTime);//獲取停止時刻計數值
105         cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;
106         runtime[i]=cost;
107         cout<<"The "<<key<<"th number is："<<t<<endl;
108         cout<<"The running time is："<<cost<<" s"<<endl;
109         free(a);
110     }
111     fout.open("data.txt");
112     if(!fout){
113         cerr<<"Can not open file 'data.txt' "<<endl;
114         return -1;
115     }
116     for(i=0;i<m;i++){
117            fout<<data_amount[i]<<","<<runtime[i]<<endl;
118     }
119     fout.close();
120     cout<<"Success!"<<endl;
121     return 0;
122 }

程式設計思路：

假設輸入的資料規模為n，要查找的資料次序為k，

（1）判斷陣列長度，若小于75則直接進行快速排序，否則進行之后的演算法，

（2）將n個輸入元素劃分成?n/5?個組，每組五個元素，用快速排序將每組中的元素排好序，并確定每組的中位數，共?n/5?個，

（3）遞回呼叫演算法Select來找出這?n/5?個元素的中位數，如果?n/5?是偶數，就找它的兩個中位數中較大的一個，以這個元素作為劃分基準，

（4）以此遞回呼叫進行排序，最終搜索得到要找的第k項，

時間復雜性分析：

為了分析演算法Select的計算時間復雜性，設n=r-p+1，即n為輸入陣列的長度，演算法的遞回呼叫只有在n≥75時才執行，因此，當n＜75是演算法Select所用的計算時間不超過一個常數C₁，找到中位數的中位數x后，演算法Select以x為劃分基準呼叫Partition對陣列a[p:r]進行劃分，這需要O（n）時間，演算法Select的for回圈體行共執行n/5次，每一次需要O（1）時間，因此，執行for回圈共需O（n）時間，

設對n個元素的陣列呼叫演算法Select需要T（n）時間，那么找中位數的中位數x至多用了T（n/5）的時間，已經證明了，按照演算法所選的基準x進行劃分所得到的2個子陣列分別至多有3n/4個元素，所以，無論對哪一個子陣列呼叫，Select都至多用了T（3n/4）的時間，

總之，可以得到關于T（n）的遞回式

解此遞回式可得T（n）=O（n），

經過5000次不同規模資料的實驗并統計運行時間得到如下演算法效率分析圖：

標籤：其他

上一篇：劍指offer筆記面試題11----旋轉陣列的最小數字

下一篇：劍指offer筆記面試題10----斐波那契數列