Sherwood-型線性時間選擇算法

1、算法分析與設計實驗報告第 次實驗實驗名稱Sherwood 型線性時間選擇算法實驗目的1. 通過上機實驗，要求掌握 Sherwood 型線性時間選擇算法的問題描述、算法設計思想、程序設計。2. 使用舍伍德型選擇算法，根據不同的輸入用例，能準確的輸出用例中的中值，并計算出程序運行所需要的時間。3. 用分治法查找數組元素的最大值和最小值實驗原理(1) 問題描述：給定任意幾組數據，利用舍伍德型選擇算法，找出數組中的中值并輸出（若數組為奇數個則輸出中值，若數組為偶數個則輸出第 n/2 小元素）。(2) 設A是一個確定性算法，當它的輸入實例為x時所需的計算時間記為tA(x)。設Xn是算法A的輸入規(guī)模為n的

2、實例的全體，則當問題的輸入規(guī)模為n時，算法A所需的平均時間為。這顯然不能排除存在xXn使得的可能性。希望獲得一個隨機化算法B，使得對問題的輸入規(guī)模為n的每一個實例均有。這就是舍伍德算法設計的基本思想。當s(n)與tA(n)相比可忽略時，舍伍德算法可獲得很好的平均性能。(3) 對于選擇問題而言,用擬中位數作為劃分基準可以保證在最壞的情況下用線性時間完成選擇。如果只簡單地用待劃分數組的第一個元素作為劃分基準，則算法的平均性能較好，而在最壞的情況下需要O(n2)計算時間。舍伍德選擇算法則隨機地選擇一個數組元素作為劃分基準，這樣既保證算法的線性時間平均性能，又避免了計算擬中位數的麻煩。(4) 用Sel

3、ect隨機產生l和r之間的一個整數作為劃分基準，對al:r中n個元素進行劃分時，第k小元素可能在低區(qū)子數組，或者剛好是劃分基準，或者在較大的子數組中。低區(qū)子數組含有一個元素的概率為2/n，含有i個元素的概率為1/n,最壞情況是第k小元素總是被劃分在較大的子數組中，此時在較大子數組中重新選擇隨機的劃分基準，找出第k小元素。(5) 舍伍德算法屬于概率算法，消除了運行時間和輸入實例之間的聯(lián)系。實驗步驟(1) 先判斷是否需要進行隨機劃分即（k（1，n）? n>1?）；(2) 產生隨機數j，選擇劃分基準，將aj與al交換；(3) 以劃分基準為軸做元素交換，使得一側數組小于基準值，另一側數組值大于基

4、準值；(4) 判斷基準值是否就是所需選擇的數，若是，則輸出；若不是對子數組重復步驟(2)(3)(4)。關鍵代碼/Sherwood.cpptemplate <typename Type>Type select(Type a, int lt, int rt, int k) / 計算alt:rt中第k小元素 static RandomNumber rnd; while(true) if(lt > rt) return alt; int i = lt, j = lt+rnd.Random(rt-lt+1); / 隨機選擇的劃分基準 Swap(ai, aj); j = rt+1; Ty

5、pe pivot = alt; /以劃分基準為軸作元素交換 while(true) while(a+i < pivot); while(a-j > pivot); if(i >= j) break; Swap(ai, aj); if(j - lt + 1 = k) return pivot; alt = aj; aj = pivot; / 對子數組重復劃分過程 if(j - lt + 1 < k) k = k - j + lt - 1; lt = j + 1; else rt = j - 1; template <typename Type>Type Sel

6、ect(Type a, int n, int k)/ 計算a0: n-1中第k小元素 / 假設an是一個鍵值無窮大的元素 if(k < 1 | k > n) cerr << "Wrong!" << endl; return select(a, 0, n-1, k);測試結果測試結果如下圖：實驗心得通過本次實驗明白了什么是舍伍德算法。知道了和開始的快速排序找第k小元素相比，舍伍德算法以高概率對任何實例均有效，算法時間不受輸入實例的影響。它的核心在于隨機選擇劃分基準，保證了算法的線性時間平均性能。從上面測試結果時間上也可以看出時間的平均性能。

7、在課本上了解了隨機洗牌算法和搜索有序表兩個部分，知道了舍伍德算法還可用于設計高效的數據結構如跳躍表，應用真的很廣泛。附錄：完整代碼(建一個項目工程)/Sherwood.cpp#include "RandomNumber.h"#include <iostream>#include <iomanip>#include <time.h>#include <stdio.h>#include <time.h>using namespace std;const int INF = 9999;/ 交換a, b的值template

8、 <typename Type>void Swap(Type &a, Type &b) Type temp; temp = a; a = b; b = temp;template <typename Type>Type select(Type a, int lt, int rt, int k) / 計算alt:rt中第k小元素 static RandomNumber rnd; while(true) if(lt > rt) return alt; int i = lt, j = lt+rnd.Random(rt-lt+1); / 隨機選擇的劃分基準

9、 Swap(ai, aj); j = rt+1; Type pivot = alt; /以劃分基準為軸作元素交換 while(true) while(a+i < pivot); while(a-j > pivot); if(i >= j) break; Swap(ai, aj); if(j - lt + 1 = k) return pivot; alt = aj; aj = pivot; / 對子數組重復劃分過程 if(j - lt + 1 < k) k = k - j + lt - 1; lt = j + 1; else rt = j - 1; template &l

10、t;typename Type>Type Select(Type a, int n, int k)/ 計算a0: n-1中第k小元素 / 假設an是一個鍵值無窮大的元素 if(k < 1 | k > n) cerr << "Wrong!" << endl; return select(a, 0, n-1, k);int main()int i,j=0; double k=0.0; clock_t start,end,over; start=clock(); end=clock(); over=end-start; start=clock(); int arr7 = 3, 2, 5, 7, 10, 4; for(i=0;i<6;i+)cout<<arri<<" " cout<<endl; cout << "第4小的元素為："<<Select(arr, 6, 4) <<