實(shí)驗(yàn)二：查找k1-k2問題實(shí)驗(yàn)報(bào)告2

1、實(shí)驗(yàn)二：用分治法查找 k1-k2問題實(shí)驗(yàn)內(nèi)容從包含n個(gè)整數(shù)的無序列表中輸出第 k1小到第k2小之間的所有整數(shù)，其中 k1=k2。分析 時(shí)間復(fù)雜度。必須用分治法求解，但是不能簡單地重復(fù)使用求第 k小元素的分治法。禁止使 用排序算法求解給出復(fù)雜度分析過程算法思想在解決實(shí)驗(yàn)的過程中參考了快速排序中雙向掃描的思想。快速排序是一種基于分治技術(shù)的重要排序算法。首先選擇一個(gè)元素，接下來根據(jù)該元素的值來劃分?jǐn)?shù)組。中軸之前的是小于中軸的數(shù)，之后的為大于中軸的數(shù)。在這個(gè)問題中我們只需要在找到中軸位K1和K2時(shí)跳出快排，輸出第K1到K2的元素，便得問題的解。在尋找中軸的過程中如果遇到k2則不需要二次快排，否則再次查

2、找中軸為k2o數(shù)據(jù)結(jié)構(gòu)：順序表 算法1Quicksort(Sqlist &L,int low,int high,int k1,int k2,int &temp)用Quicksort對(duì)子數(shù)組排序快排到中軸為k1返回輸出：k1將數(shù)組分為k1前和k1后兩部分if(lowk1)如果k1小于中軸，對(duì)low到s-1部分快排 if(s=k2)temp=1;中軸為k2記錄temp為真 Quicksort(L,low,s-1,k1,k2,temp); else if(sk1)如果k1大于中軸，對(duì) s到high部分快排 Quicksort(L,s+1,high,k1,k2,temp); else if(s=k1)

3、如果k1等于于中軸跳出遞歸將數(shù)組分為大于k1和小于k2兩部分return ;Partition(Sqlist &L,int low,int high)以L.elem0為限位器，以第一個(gè)元素為中軸，輸入：順序表的子順序表 L.elemlow-high輸出：順序表的一個(gè)分區(qū)，分裂點(diǎn)的位置作為函數(shù)的返回值while(lowhigh)while(low=pivotkey)從表的兩端交替地向中間掃描-high；L.elemlow=L.elemhigh;/將比中軸小的記錄交替到低端while(lowhigh & L.elemlow=pivotkey)+low;L.elemhigh=L.elemlow;/將

4、比中軸大的記錄交替到高端 L.elemlow=L.elem0;/ 中軸記錄到位 return low;實(shí)驗(yàn)過程1、源程序*/*/*從包含n個(gè)整數(shù)的無序列表中輸出第K1小道第k2小之間的所有整數(shù)，其中*k1=k2,分析時(shí)間復(fù)雜度，在這里采用快排的思想分別找出中軸為k1和*k2*/* 時(shí)輸出 k1 和 k2 之間的數(shù)，便為所需*88#includeusing namespace std;/* 結(jié)構(gòu)體 *struct Sqlistint *elem;/元素指針int length;/ 長度int listsize;/;/*構(gòu)造一個(gè)空的線性順序表*void InitList_Sq(Sqlist &L)

5、L.elem=(int *)malloc(100*sizeof(int);/開辟空間L.length=0;L.listsize=100;/ 初始化/*快排的分區(qū)過程 *int Partition(Sqlist &L,int low,int high)int pivotkey;L.elem0=L.elemlow; 以 L.elem0為限位器 pivotkey=L.elemlow;以第一個(gè)元素為中軸 while(lowhigh)/從表的兩端交替地向中間掃描 while(low=pivotkey)-high；L.elemlow=L.elemhigh;/將比中軸小的記錄交替到低端 while(lowh

6、igh & L.elemlow=pivotkey)+low;L.elemhigh=L.elemlow;/將比中軸大的記錄交替到高端 L.elemlow=L.elem0;/ 中軸記錄到位return low;/返回中軸位置 /*用遞歸選擇中軸，根據(jù)中軸調(diào)用函數(shù) int Partition(Sqlist &L,int low,int high) 分區(qū),當(dāng)中軸為K1時(shí)跳出遞歸*void Quicksort(Sqlist &L,int low,int high,int k1,int k2,int &temp) int s;if(lowk1)如果k1小于中軸，對(duì)low到s-1部分快排if(s=k2)te

7、mp=1;Quicksort(L,low,s-1,k1,k2,temp);else if(sk1)如果k1大于中軸，對(duì) s到high部分快排Quicksort(L,s+1,high,k1,k2,temp);else if(s=k1)如果k1等于于中軸跳出遞歸將數(shù)組分為大于k1和小于k2兩部分return ; void Print(Sqlist L,int k1,int k2) /*打印第k1小到k2小的元素*for(int i=k1;i=k2;i+) coutL.elemi coutendl;/* 主函數(shù) *int main()int n,k1,k2,temp=0;Sqlist List;In

8、itList_Sq(List);/ 初始化順序表cout請(qǐng)輸入無序數(shù)列中整數(shù)的個(gè)數(shù)：n;cout請(qǐng)以空格鍵隔開輸入無序數(shù)列：endl;/用戶輸入無序列表for(int i=1;iList.elemi;cout您輸入的無序數(shù)列為：endl;Print(List,1,n); 打印序列cout請(qǐng)輸入輸出整數(shù)的范圍：(如第4小到的8?。? 8 ) k1k2;Quicksort(List,1,n,k1,k2,temp);/*一次快排cout當(dāng)找到中軸為k1后整數(shù)的排列情況endl;Print(List,1,n);/*次快排后數(shù)組情況if(temp)/在找到中軸為k1前已經(jīng)遇到k2為中軸cout在找到中軸為k1前已經(jīng)遇到k2為中軸，所以第 K1小到第k2小之間的所 有整數(shù)為：endl;Print(List,k1,k2);else/位遇到k1之前并未遇到k2所以再次快排分區(qū)Quicksort(List,k1,n,k2,k1,temp);/* 二次快排cout在找到中軸為k1前未遇到k2為中軸，通過找k2為中軸后整數(shù)的排列情況 為：endl;Print(List,1,n);cout第K1小到第k2小之間的所有整數(shù)為：1時(shí)，最差：C (n) =C(n-1)+n=n*n