排序算法比較程序

1、1 #include #include #include #include #include #define max 100000000 using namespace std; void print(long r,long n) for(int i=1;i=n;i+) coutsetw(4)1) long lastexchangeindex=1;/ 表示已經(jīng)有序for(long j=1;ji;j+) if(rj+1rj) long t=rj; rj=rj+1; rj+1=t; bt+; lastexchangeindex=j;/記下進(jìn)行的位置 i=lastexchangeindex;/本趟進(jìn)

2、行過交換的最后一個記錄的位置cout第y 趟:; y+; for(long x=1;x=i;x+) coutsetw(4)rx; coutsetw(3)ri+1; for(x=i+2;x=n;x+) coutsetw(4)rx; cout; coutendl; 2 return bt; /- /選擇排序/- /static long st=0; long selectminkey(long r,long i,long n)/在 ri.r.length 中選擇關(guān)鍵字最小的記錄 long temp=i;/記錄最小的元素值的位置for(int j=i;jrj) temp=j; /st+; retur

3、n temp; long selectsort(long r,long n) long j,i,t; long y=1; int st=0; for( i=1;in;i+) j = selectminkey(r,i,n);/ 在 l.ri.l.length 中選擇關(guān)鍵字最小的記錄if (i!=j) / 與第 i 個記錄交換 t=ri; ri=rj; rj=t; st+; cout第y 趟: ; y+; for(long x=1;x=i;x+) coutsetw(4)rx; coutsetw(3)ri+1; for(x=i+2;x=n;x+) coutsetw(4)rx; cout; 3 /pr

4、int(r,n); coutendl; return st; /- /直接插入排序/- long insertsort(long r, long n) long y=1; long it=0,j; for(long i=2;i=n;+i) if(riri-1) r0=ri;/ 復(fù)制為哨兵it=it+1; for( j=i-1;r0rj;-j) rj+1=rj;/ 記錄后移it=it+1; rj+1=r0;/ 插入到正確位置it=it+1; cout第y 趟: ; y+; coutsetw(4)r1; for(long x=2;x=i;x+) coutsetw(4)rx; cout; for(x

5、=i+1;x=n;x+) coutsetw(4)rx; coutendl; return it; /- / 快速排序/- static long qt=0; int partition (long r, long low, long high,long n) 4 r0 =rlow; long pivotkey = rlow; / 樞軸qt=qt+2; while (lowhigh) while(low=pivotkey)/ 從右向左搜索- high; rlow = rhigh; qt=qt+1; while (lowhigh & rlow=pivotkey)/ 從左向右搜索+ low;

6、 rhigh = rlow; qt=qt+1; rlow =r0; qt=qt+1; return low; / partition void quicksort (long r, int low, int high,long n,long y)/ 對記錄序列l(wèi).rlow.high 進(jìn)行快速排序 if (low high) / 長度大于 1 long pivotloc = partition(r,low,high,n);/ 對 l.rlow.high 進(jìn)行一次劃分qt=qt+1; cout第y 趟:; y+; print(r,pivotloc-1); coutsetw(2)rpivotloc;

7、 cout; for(long x=pivotloc+1;x=n;x+) coutsetw(5)rx; coutendl; quicksort(r, low, pivotloc-1,n,y); / 對低子序列遞歸排序quicksort(r, pivotloc+1, high,n,y); / 對高子序列遞歸排序 / qsort void quicksort(long r,long n) 5 long y=1; quicksort(r,1,n,n,y); /- /操作選擇函數(shù)/- void operate(long a, long n) void main(); long * r = new lo

8、ng n; time_t start, end;/定義兩個變量double time;/排序時(shí)間long degree;/排序次數(shù)char ch; cout ch; switch(ch) case 1: coutn; coutt=您選擇的是冒泡排序 =n; for(int i = 1; i =n; i +)/ 將隨機(jī)數(shù)付給 ri ri = ai; start=(double)clock(); degree = bubblesort(r, n); end=(double)clock(); time = (double)(end-start)/clk_tck; /print(r,n); cout

9、n; cout 冒泡排序所用時(shí)間： t time n; cout 冒泡排序交換次數(shù)： t degree n; coutn; operate(a, n); break; case 2: coutn; coutt=您選擇的是選擇排序 =n; for(int i = 1; i = n; i +) ri = ai; 6 start=(double)clock(); degree = selectsort(r, n); end=(double)clock(); time = (double)(end-start)/clk_tck; /print(r,n); coutn; cout 選擇排序所用時(shí)間： t

10、 time n; cout 選擇排序交換次數(shù)： t degree n; cout n; operate(a, n); break; case 3: coutn; coutt=您選擇的是直接插入排序=n; for(int i=1; i=n; i +) ri = ai; start=(double)clock(); degree = insertsort(r, n); end=(double)clock(); time = (double)(end-start)/clk_tck; /print(r,n); coutn; cout 直接插入排序所用時(shí)間： time n; cout 直接插入排序交換次

11、數(shù)： degree n; cout n; operate(a, n); break; case 4: coutn; coutt=您選擇的是快速排序 =n; for(int i=1; i=n; i +) ri = ai; start=(double)clock(); quicksort(r, n); end=(double)clock(); 7 time = (double)(end-start)/clk_tck; coutn; cout 快速排序所用時(shí)間： t time n; cout 快速排序交換次數(shù)： t qt n; cout n; operate(a, n); break; case a

12、: main(); break; default: cout 輸入錯誤，請選擇正確的操作！ n; operate(a, n); break; case 0: cout您已選擇退出程序，謝謝使用n; break; /- /導(dǎo)航菜單函數(shù)/- void daohang() coutn* 排序算法比較*endl; cout*endl; cout= 1 - 冒泡排序=endl; cout= 2 - 選擇排序=endl; cout= 3 - 直接插入排序=endl; cout= 4 - 快速排序=endl; cout= 0 - 退出程序=endl; cout= a - 改變隨機(jī)數(shù)的個數(shù)=endl; cou

13、t*endl; /- 8 /隨機(jī)輸入函數(shù)/- void rand() cout n 請輸入要產(chǎn)生的隨機(jī)數(shù)的個數(shù)（0=n=100000000） ： n; cout endl; long *a = new long n; srand(unsigned long)time(null);/產(chǎn)生一個以當(dāng)前時(shí)間開始的隨機(jī)種子for (long i=1; i=n; i+) ai = rand() % n;/n 為最大值 ,其隨機(jī)域?yàn)?0n-1 daohang(); print(a,n); operate(a, n); /- /手動輸入函數(shù)/- void handinput() cout請輸入數(shù)據(jù)個數(shù)： endl; int n; coutn; cout endl; long *a = new long