數(shù)據(jù)結(jié)構(gòu)實驗8排序

實驗八排序一、實驗目的1.熟悉掌握教材中所介紹的幾種排序方法。2.學會分析各種內(nèi)排序算法的性能。二、實驗內(nèi)容隨機產(chǎn)生20位整數(shù)輸入序列，編寫程序，按下列排序方法將序列從小到大排序并輸出。冒泡排序快速排序紀錄每種方法比較次數(shù)和移動次數(shù)三、實驗步驟1、冒泡排序冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即首先比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。重復以上過程，仍從第一對數(shù)開始比較。如此下去，直至最終完成排序。 2、快速排序基本思想快速排序（Quicksort）是對冒泡排序的一種改進。由C.A.R.Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。實現(xiàn)方法設要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。一趟快速排序的算法是：1）設置兩個變量I、J，排序開始的時候：I=1，J=N-1；2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給X，即X=A[0]；3）從J開始向前搜索，即由后開始向前搜索（J=J-1），找到第一個小于X的值，讓該值與X交換；4）從I開始向后搜索，即由前開始向后搜索（I=I+1），找到第一個大于X的值，讓該值與X交換；5）重復第3、4步，直到I=J；算法說明首先為了避免產(chǎn)生的隨機數(shù)過大，我們限定了了隨機數(shù)為1-100之間，其次我們分別運用函數(shù)產(chǎn)生隨機數(shù)兩次，第一次為使用冒泡排序，第二次為使用快速排序。測試結(jié)果分析與探討在設計中除了注意冒泡排序和快速排序的原理外，還需要注意函數(shù)間的套用中出現(xiàn)的形參和實參的類型統(tǒng)一，以及交換兩個數(shù)值時候，中介參數(shù)的使用。附錄：源代碼源代碼列在附錄中，要求程序風格清晰易理解，有充分的注釋。有意義的注釋行不少于30%。#include"stdio.h"#include"time.h"#include"stdlib.h"#include"iostream"usingnamespacestd;voidQuickSort(intp[],intstart,intend){if(start>=end){return;}inti=0,j=0,tmp=0;i=start;j=end-1;do{while(p[i]<p[end]){i++;}while(p[j]>=p[end]){j--;}if(i<j){tmp=p[i];p[i]=p[j];p[j]=tmp;}else{tmp=p[i];p[i]=p[end];p[end]=tmp;}}while(i<j);QuickSort(p,start,i-1);QuickSort(p,i+1,end);}voidPrintArrary(intdata[],intsize){for(inti=0;i<size;++i){cout<<data[i]<<"";}cout<<endl;}voidmain(){ inta[20],i,j,t,flag; intargc[20]; srand((unsigned)time(0)); for(i=0;i<20;i++) a[i]=rand()%100; cout<<"隨機產(chǎn)生20個100以內(nèi)的整數(shù)"<<endl; for(i=0;i<20;i++) cout<<a[i]<<""; for(i=0;i<19;i++)/*改進型冒泡法排序*/ { flag=0; for(j=0;j<20-i-1;j++) if(a[j]>a[j+1]) { t=a[j];/*交換a[i]和a[j]*/ a[j]=a[j+1]; a[j+1]=t; flag=1; } if(flag==0)break; } cout<<endl; cout<<"將這20個整數(shù)按照冒泡排序進行升序排列"<<endl; for(i=0;i<20;i++) cout<<a[i]<<""; cout<<endl; for(i=0;i<20;i++) argc[i]=rand()%100; cout<<"再次隨機產(chǎn)生20個100以內(nèi)的整數(shù)"<<endl; Pr