1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)： 實(shí)驗(yàn)3排序?qū)W生姓名： 滿(mǎn)興源班 級(jí)： 2014211105班內(nèi)序號(hào)： 15學(xué) 號(hào)： 2014210128日 期： 2015年12月28日1 實(shí)驗(yàn)要求使用簡(jiǎn)單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：1、插入排序2、希爾排序3、冒泡排序4、快速排序5、簡(jiǎn)單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求：1、測(cè)試數(shù)據(jù)分成三類(lèi)：正序、逆序、隨機(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ù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到

2、微秒（選作）4、對(duì)2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時(shí)間復(fù)雜度編寫(xiě)測(cè)試main()函數(shù)測(cè)試排序算法的正確性。2.1 存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)數(shù)組2.2 關(guān)鍵算法分析1. 插入排序：依次將待排序的序列中的每一個(gè)記錄插入到先前排序好的序列中，直到全部記錄排序完畢void Insertsort(int r, int n)for (int i = 2; i <= n; i+)if (ri < ri - 1)int j;r0 = ri;ri = ri - 1;for (j = i - 2; r0 < rj; j-)rj + 1 = rj;rj + 1 = r0;2. 希爾排序：先將

3、整個(gè)序列分割成若干個(gè)子列，分別在各個(gè)子列中運(yùn)用直接插入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序void ShellInsert(int r, int n)int j;for (int d = n / 2; d >= 1; d = d / 2)for (int i = d + 1; i <= n; i+)if (ri < ri - 1)r0 = ri;for (j = i - d; j>0 && r0<rj; j = j - d)rj + d = rj;rj + d = r0;3. 冒泡排序：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交

4、換，直到?jīng)]有反序記錄為止void BubbleSort(int r, int n)int pos = n;while (pos != 0)int bound = pos;pos = 0;for (int i = 1; i < bound; i+)if (ri>ri + 1)r0 = ri;ri = ri + 1;ri + 1 = r0;pos = i;4. 快速排序：首先選擇一個(gè)基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對(duì)兩部分重復(fù)上述過(guò)程，直至整個(gè)序列排序完成int Partion(int r, int first, int end)int i = fir

5、st;int j = end;int pivot = ri;while (i < j)while (i < j) && (rj >= pivot)j-;ri = rj;while (i < j) && (ri <= pivot)i+;rj = ri;ri = pivot;return i;void QSort(int r, int i, int j)if (i <j)int pivotloc = Partion(r, i, j);QSort(r, i, pivotloc - 1);QSort(r, pivotloc + 1,

6、j);5. 選擇排序：從待排序的記錄序列中選擇關(guān)鍵碼最小的記錄并將它與序列中的第一個(gè)記錄交換位置；然后從不包括第一個(gè)位置上的記錄序列中選擇關(guān)鍵碼最小（或最大）的記錄并將它與序列中的第二個(gè)記錄交換位置；如此重復(fù)，直到序列中只剩下一個(gè)記錄為止void SelectSort(int r, int n)for (int i = 1; i < n; i+)int index = i;for (int j = i + 1; j <= n; j+)if (rj < rindex)index = j;if (index != i)r0 = ri;ri = rindex;rindex = r0

7、;用戶(hù)輸入數(shù)組開(kāi)始3. 程序運(yùn)行結(jié)果3.1主函數(shù)流程圖五種排序輸出結(jié)果結(jié)束3.2程序運(yùn)行框圖源代碼：#include<iostream>using namespace std;void print(int r, int n)for (int i = 1; i <= n; i+)cout << ri << " "cout << endl;/*插入排序*/void Insertsort(int r, int n)for (int i = 2; i <= n; i+)if (ri < ri - 1)int j;r0

8、 = ri;ri = ri - 1;for (j = i - 2; r0 < rj; j-)rj + 1 = rj;rj + 1 = r0;/*希爾排序*/void ShellInsert(int r, int n)int j;for (int d = n / 2; d >= 1; d = d / 2)for (int i = d + 1; i <= n; i+)if (ri < ri - 1)r0 = ri;for (j = i - d; j>0 && r0<rj; j = j - d)rj + d = rj;rj + d = r0;/*改

9、進(jìn)的冒泡排序*/void BubbleSort(int r, int n)int pos = n;while (pos != 0)int bound = pos;pos = 0;for (int i = 1; i < bound; i+)if (ri>ri + 1)r0 = ri;ri = ri + 1;ri + 1 = r0;pos = i;/*快速排序*/int Partion(int r, int first, int end)int i = first;int j = end;int pivot = ri;while (i < j)while (i < j) &

10、amp;& (rj >= pivot)j-;ri = rj;while (i < j) && (ri <= pivot)i+;rj = ri;ri = pivot;return i;void QSort(int r, int i, int j)if (i <j)int pivotloc = Partion(r, i, j);QSort(r, i, pivotloc - 1);QSort(r, pivotloc + 1, j);/*簡(jiǎn)單選擇排序*/void SelectSort(int r, int n)for (int i = 1; i <

11、 n; i+)int index = i;for (int j = i + 1; j <= n; j+)if (rj < rindex)index = j;if (index != i)r0 = ri;ri = rindex;rindex = r0;void main()int x;int n = 10;int rr11 ,a11 ;rr0 = -1;cout << "請(qǐng)輸入需要排序的數(shù)組："for (int i = 1; i <= 10; i+)cin >> x;rri = x;for (int i = 1; i <= 10

12、; i+)ai = rri;Insertsort(rr, n);cout << "插入排序法排序后的數(shù)為：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;ShellInsert(rr, n);cout << "希爾排序法排序后的數(shù)為：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;BubbleSort(rr, n);cout << &qu

13、ot;冒泡排序法(改進(jìn)）排序后的數(shù)為：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;QSort(rr, 1, n);cout << "快速排序法排序后的數(shù)為：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;SelectSort(rr, n);cout << "簡(jiǎn)單選擇排序法排序后的數(shù)為：" << endl;print(rr, 10);for (int i = 1; i <= 10; i+)rri = ai;4. 總結(jié)1.調(diào)試時(shí)出