北郵數(shù)據(jù)結(jié)構(gòu)實驗報告-排序

1、北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)測試報告實驗名稱：實驗4的排序?qū)W生姓名：班級級別：班級編號：號碼：日期：2014年1月4日實驗的目的學(xué)習(xí)、實現(xiàn)和比較各種排序算法，掌握各種排序算法的優(yōu)缺點，以及各種算法的使用。2實驗內(nèi)容2.1主題1使用簡單數(shù)組來實現(xiàn)以下排序算法并進行比較。排序算法：1.插入排序2.希爾排名3、氣泡排序4.快速排序5、簡單選擇排序6.堆排序(可選)7、合并排序(可選)8.基數(shù)排序(可選)9.其他的要求：1.測試數(shù)據(jù)分為三類：正序、負(fù)序和隨機數(shù)據(jù)2.對于這三種類型的數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較時間和移動時間(其中關(guān)鍵字交換計為3次移動)。3.對于這三種類型的數(shù)據(jù)，將上述排序算法中不同算

2、法的執(zhí)行時間與微秒(可選)進行比較4.分析2和3的結(jié)果，驗證上述算法的時間復(fù)雜度編寫并測試main()函數(shù)，以測試線性表的正確性。3程序分析3.1存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)陣列3.2關(guān)鍵算法分析1.插入排序：將要排序的序列中的每條記錄插入到之前排序的序列中，直到所有記錄都被排序完畢Void insertsort (intr ，intn，int * compare，int * move)/insert sort* compare=0；* move=0；int I；int j；對于(I=1；I=0；j -)(*比較)；(*移動)；rj 1=rj；如果(j=0)(*比較)；rj 1=x；2.希爾排序：首先

3、，將整個序列分成幾個子列，并對每個子列應(yīng)用直接插入排序。當(dāng)整個序列基本有序時，直接插入排序再次應(yīng)用于所有記錄空隙殼插入(intr ，intn，int * compare，int * move)/希爾排序* compare=0；* move=0；int j；對于(int d=n/2；d=1；/間距越來越小對于(int I=d；I=n-1；/決定是否從d開始逐個元素地向前移動if(rI=0)(x=0)(*比較)；rj d=x；否則(*比較)；3.冒泡排序：成對比較相鄰記錄的關(guān)鍵字，如果順序顛倒，則交換它們，直到?jīng)]有顛倒順序的記錄。空氣泡排序(intr ，intn，int * compare，int

4、 * move)/交換(氣泡)排序* compare=0；* move=0；int x；對于(int j=0；jj；i -)如果(ri=zhou) /查看右邊元素和軸之間的大小關(guān)系(*比較)；j-；如果(I使用命名空間標(biāo)準(zhǔn)；void Insertsort(int r，int n，int* compare，int * move)；void ShellInsert(int r，int n，int* compare，int * move)；void Bubblesort(int r，int n，int* compare，int * move)；int Partion(int r，int first，int end，int* compare，int * move)；void Qsort(int r，int i，int j，int* compare，int * move)；void Selectsort(int r，int n，int* compare，int * move)；void main()int I；int compare=0；int move=0；Cout 首先輸入一個正序數(shù)組 n；int * r=新intn；“Cout”請在數(shù)組中輸入元素