1、問題描述

給定的線性集中n個元素和一個正整數k(1≤k≤n)，要求在線性時間內（即時間復雜度為O(n）)找出這n個元素中第k小的元素。

2、算法設計思想

將n個元素劃分成n/5組，每組5個元素，只可能有一組不是5個元素。再用冒泡排序法，將每組內的五個元素排好序，取出其中位數，共n/5個。
然后遞歸調用Select方法找出這n/5個數中的中位數。若n/5是偶數，就找其最大的數。以這個元素作為劃分標準。判斷k與n的位置，再進行下一步的劃分。

3、算法過程描述

以[8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,
16,5,41,7,23,22,46,29]為例查找這29個元素中的第18個元素：
(1)把這29個元素分成6組：
(8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7),(23,22,46,29)
(2)取出每一組的中位數，為31，49，13，25，16
(3)遞歸出的中值為25
(4)根據25將29個元素劃分為3個子數組：
P = {8,4,11,17,3,13,6,19,16,5,7,23,22}
Q = {25}
L = {31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}
(5)因為|p| = 13,|Q| = 1,18>13 +1,所以第18個元素在L區域，找第18-13-1=4個元素，對L遞歸；
(6)將L劃分成3組：
{31,60,33,51,57}{49,35,43,37,52}{32,54,41,46,29}
(7)取出每一組的中位數，為51，43，41遞歸出的中值為43
(8)根據43將L組劃分為3個子數組：
{31,33,35,37,32,41,29}
{43}
{60,51,57,49,52,54,41,46}
(9)因為第一個子數組中的元素的個數大于4，所以第18個元素在第一個子數組中，對第一個子數組遞歸；
(10)將第一個子數組分成了1組：
{31,33,35,37,32}
(11)取出中位數為33；
(12)根據33將第一個子數組分成3個子數組：
{31,32,29}
{33}
{35,3,41}
(13)因為第一個，第二個子數組的元素的個數之和為4，所以33即為所求的第18個元素。

4、算法實現及運行結果

（一）代碼實現：

#include <stdio.h> #define SIZE (29) //主函數 int main (void); //遞歸分組 int Select(int array[],int left,int right,int ith); //尋找中位數 int Findmiddata(int array[],int left,int right); //排序取中位數下標 int InsertSort(int array[],int a,int b); //分組，以中位數為界，將比中位數小的放在左邊，比中位數大的放在右邊 int Partition(int array[],int left,int right,int mid); //交換 void swap (int array[],int a,int b);int main(void){//數組 int array[SIZE] = {8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29} ; int size = SIZE ; int ith = 18 ; for(int i = 0;i < size;i++){printf("%d ",array[i]); }printf("\n");printf("該數組的第%d位的元素是：%d\n",ith,Select(array,0,size - 1,ith)); }//遞歸分組 int Select(int array[],int left,int right,int ith){int findMiddateMid = Findmiddata(array,left,right);int PartitionMid = Partition(array,left,right,findMiddateMid);if(PartitionMid == ith - 1){return array[PartitionMid];}if(PartitionMid < ith - 1){Select(array,PartitionMid + 1,right,ith);}else{Select(array,left,PartitionMid - 1,ith);} }//尋找中位數 int Findmiddata(int array[],int left,int right){int i,mid;for(i = 0;i <= (right - left)/5;i++){if((left + i * 5 + 4) < right){mid = InsertSort(array,left + i * 5, left + i * 5 + 4);}swap(array,i,mid);}mid = InsertSort(array,0,(right - left) / 5);return mid; }//排序取中位數下標 int InsertSort(int array[],int a,int b){int i,j;//冒泡排序 for(i = a; i < b - 1; i++){for(j = i + 1; j < b;j++){if(array[i] > array[j]){swap(array,i,j);}}}//取中位數的下標 if((b - a + 1) % 2 == 0){return (b + a) / 2 + 1; }else{return (b + a) / 2;} }//分組，以中位數為界，將比中位數小的放在左邊，比中位數大的放在右邊 int Partition(int array[],int left,int right,int mid){int value = array[mid];int i = left;int j = right;int size = SIZE ; while(1){while (array[i] < value){i++;}while (array[j] > value){j--;}if (i < j) swap(array,i,j) ; else break ; }for(int k = 0; k < size;k++){if(array[k] == value){mid = k;} }return mid; }//交換 void swap (int array[],int a,int b){ int temp ; temp = array[a]; array[a] = array[b] ; array[b] = temp ; }

（二）運行結果：

**

5、算法復雜度分析

**
（1）時間復雜度
上述算法中，設n = r - p + 1,即n為輸入數組的長度，算法的遞歸調用只有在n>=75時執行。因此，當n<75時，算法Select所用的計算時間不超過一個常數，找到中位數的中位數x后，算法Select以x為劃分基準調用函數Partition對數組進行劃分，這需要O（n)時間。算法Select的循環共執行n/5次，每一次要O（1）時間，因此，共需O（n）時間。
設對n個元素的數組調用Select需要T（n）時間，那么找中位數的中位數x至少要T（n/5）時間。先以證明，按照算法所選的基準x進行劃分所得的兩個子數組分別至多有3n/4個元素，所以無論對哪個子數組調用Select都至多用T
（3n/4）時間。
所以算法的時間復雜度為
T（n） ≤
由此可得T(n)=O( n ).
（2）空間復雜度
算法在歸并過程中，共需要n個輔助存儲空間來臨時保存合并的結果。所以空間復雜度S(n)= O(n)

總結

以上是生活随笔為你收集整理的线性时间选择问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。