北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-排序

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

2、法的執(zhí)行時(shí)間與微秒(可選)進(jìn)行比較4.分析2和3的結(jié)果，驗(yàn)證上述算法的時(shí)間復(fù)雜度編寫(xiě)并測(cè)試main()函數(shù)，以測(cè)試線(xiàn)性表的正確性。3程序分析3.1存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(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；對(duì)于(I=1；I=0；j -)(*比較)；(*移動(dòng))；rj 1=rj；如果(j=0)(*比較)；rj 1=x；2.希爾排序：首先

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

4、 * move)/交換(氣泡)排序* compare=0；* move=0；int x；對(duì)于(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 首先輸入一個(gè)正序數(shù)組 n；int * r=新intn；“Cout”請(qǐng)?jiān)跀?shù)組中輸入元素