二分搜索算法和快速排序算法及分治策略

1、實驗課程：算法分析與設計 實驗名稱：實驗二 c/c+環(huán)境及遞歸算法 （綜合性/設計性）實驗目標：1、熟悉二分搜索算法和快速排序算法；2、初步掌握分治算法；實驗任務：掌握分治策略的概念和基本思想。實驗題：1、 設a0:n-1是一個已排好序的數(shù)組。請改寫二分搜索算法，使得當搜索元素x不在數(shù)組中時，返回小于x的最大元素的位置i和大于x的最小元素位置j。當搜索元素在數(shù)組中時，i和j相同，均為x在數(shù)組中的位置。設有n個不同的整數(shù)排好序后存放于t0:n-1中，若存在一個下標i，0in，使得ti=i，設計一個有效的算法找到這個下標。要求算法在最壞的情況下的計算時間為o（logn）。2、 在快速排序中，記錄的

2、比較和交換是從兩端向中間進行的，關鍵字較大的記錄一次就能交換到后面單元，關鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。實驗設備及環(huán)境：pc；c/c+的編程環(huán)境visual c+。實驗主要步驟：(1) 明確實驗目標和具體任務；(2) 理解實驗所涉及的分治算法；(3) 編寫程序并實現(xiàn)分治算法；(4) 設計實驗數(shù)據(jù)并運行程序、記錄運行的結(jié)果；實驗數(shù)據(jù)及運行結(jié)果、實驗結(jié)果分析及結(jié)論：1、#include <iostream>using namespace std;int main()int const length=100;int n,x;in

3、t alength;cout<<"依次輸入數(shù)組的長度，數(shù)組內(nèi)容，要查找的數(shù)"<<endl;cin>>n; /輸入數(shù)組的長度for(int i=0;i<n;i+)cin>>ai;cin>>x; void binarysearch(int a,int n,int x); binarysearch(a, n, x);return 0;void binarysearch(int a,int n,int x) /n:數(shù)組長度，i，j分別表示下標 int i,j,mid=0,left=0; int right=n-1;

4、while(left<right+1&&left>=0) int mid=(left+right)/2; if(x=amid)i=j=mid;break; if(x>amid)left=mid+1;elseright=mid-1; if (i=j)&&(i>=0)cout<<"所找的數(shù)據(jù)在數(shù)組中下標為："<<i<<endl;elsei=right;j=left;cout<<"所找的數(shù)據(jù)不在數(shù)組中，其前后下標為："<<i<<

5、9;,'<<j<<endl;實驗結(jié)果： 結(jié)果分析：數(shù)據(jù)為數(shù)組長度為5，數(shù)組內(nèi)容為1，2，3，4,5和1,2,3,6,8，當要查詢的是4時，顯示的結(jié)果為在第3位和不存在的情況下前后下標為2,3，因而可知程序執(zhí)行是正確的。2、#include <iostream>using namespace std;#define num 1000int anum;template<class type>void quicksort(type a, int p, int r)if (p < r)int q = partition(a, p, r);q

6、uicksort(a, p, q - 1);/ 對左半段排序quicksort(a, q + 1, r);/ 對右半段排序template<class type>int partition(type a, int p, int r)int i = p, j = r + 1;type x = ap;/ 將<x的元素交換到左邊區(qū)域/ 將>x的元素交換到右邊區(qū)域while (true)while (a+i < x);while (a-j > x);if (i >= j)break;swap(ai, aj);ap = aj;aj = x;return j;void main()int n;cout<<"請輸入數(shù)組大?。?quot;<<endl;cin>>n;cout<<"請輸入數(shù)組的內(nèi)容并以空格隔開："<<endl;for(int z=0;z<n;z+)cin>>az;cout<<"從小到大排序后為:"quicksort(a, 0, n-1);for (int i = 0;i < n; +i)if (i != n-1)cout << ai << &