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

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱： 實驗四排序?qū)W生姓名： 班 級： 班內(nèi)序號：學 號： 日 期： 2013年12月16日1 實驗要求使用簡單數(shù)組實現(xiàn)下面各種排序算法，并進行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計為3次移動）。 3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微秒（選作）4、對2和3的結(jié)果進行分析，驗證上述各種算法的時間復雜度編寫測

2、試main()函數(shù)測試線性表的正確性。2. 程序分析2.1 存儲結(jié)構(gòu)使用最簡單的一維數(shù)組存儲待排序的數(shù)據(jù)。共使用三個數(shù)組，一個用來構(gòu)造正序數(shù)組，一個是逆序數(shù)組，還有一個是隨機數(shù)組。每種排序使用的數(shù)組都是具有相同初始值的，因而使得試驗結(jié)果具有可比較性。2.2關(guān)鍵算法分析  2.2.1 插入排序算法插入排序的思想是：每次從無序區(qū)取一元素將其添加到有序區(qū)中。2.2.2 希爾排序算法 希爾排序是一種縮小增量排序的算法，首先將待排序元素集按照一定間隔分成多個子集，分別對這些子集進行直接插入排序，整個序列部分有序。然后縮小間隔，在進行直接插入排序，直到間隔

3、為1，此時，整個序列已全部有序。 2.2.3 起泡排序 起泡排序的思想是：兩兩比較相鄰的元素，如果反序，則交換次序，直到?jīng)]有反序的元素為止。 在此思想指導下首先將待排序元素劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)所有待排序素；             對無序區(qū)從前向后依次將相鄰元素關(guān)鍵碼進行比較，若反序，則交換          

4、   重復執(zhí)行直到無序區(qū)中沒有元素。     2.2.4快速排序算法 2,2,4,1一趟快速排序算法自然語言描述如下  選取區(qū)間第一個元素作為軸值  讀取區(qū)間首尾坐標，并將其左右側(cè)待比較元素  右側(cè)掃描：從后向前找到第一個比軸值小的元素，和左側(cè)待比較元素交換（左側(cè)第一個帶比較元素為軸值）  左側(cè)掃描：從前向后找到第一個比軸值大的元素，和右側(cè)待比較元素交換  重復，直到左右兩側(cè)帶比較元素的坐標相等 

5、其c+描述如下2.2.4.2完整的快速排序算法如下：2.2.5選擇排序算法 選擇排序自然語言描述如下：  在r1rn待排序元素序列中選出最小記錄，將其與第一個元素rn交換  在r2rn待排序元素序列中選出最小記錄，將其與第一個元素ri交換   直至rn-1rn C+描述如下： 2.2.6堆排序 2.2.6.1堆的建立，按照小根堆的定義建立堆的算法如下   說明：根節(jié)點存放在r1中，ri的左孩子為r2*i,右孩子為r2*i+1 2.2.6.2調(diào)整數(shù)

6、組為升序排列    輸出堆頂元素 將堆中最后一個元素移至堆頂，并將剩余元素調(diào)整為小根堆    反復執(zhí)行兩個元素，直到堆中只有一個元素  2.2.6.2堆排序完整算法如下 3. 程序運行結(jié)果測試主函數(shù)運行流程圖： 源代碼#include<iostream>#include"time.h"using namespace std;void InsertSort(int r, int n)/直接插入排序 int count1 = 0, count2 =

7、 0;/分別用來記錄插入排序比較和移動次數(shù)的計數(shù)器 for (int i = 2; i <= n - 1; i+)if (ri<ri - 1)/查找插入位置 r0 = ri; /設(shè)置哨兵 count2+; /移動次數(shù)加1int j;for (j = i - 1; count1+, r0<rj; j-) /尋找插入位置 rj + 1 = rj; /元素后移 count2+; /移動次數(shù)加1rj + 1 = r0;/插入記錄 count2+;else count1+;/此時雖然沒有移動但是已經(jīng)進行了一次比較 cout << "比較" <<

8、; count1 << "移動" << count2;void ShellSort(int r, int n) /希爾排序 int i, d, j;int count1 = 0, count2 = 0;for (d = n / 2; d >= 1; d = d / 2) /以增量為d進行直接插入排序 for (i = d + 1; i<n; i+) /一趟希爾排序 r0 = ri; /暫存被插入記錄 for (j = i - d; j>0 && r0<rj; j = j - d)/每隔d個記錄進行一次比較和移動

9、 rj + d = rj; /記錄后移d個位置 rj + d = r0;count1+;count2 = count2 + d;/每次都移動d個位置 count1+;cout << "比較" << count1 << "移動" << count2; void BubbleSort(int r, int n) /起泡排序 int temp, pos, bound;int count1 = 0, count2 = 0;pos = n - 1; /第一趟起泡排序的范圍是r1到rn while (pos != 0)

10、 /僅當上一趟排序有記錄交換才進行本趟排序 bound = pos; /本次無序元素的范圍 pos = 0; /控制外循環(huán)結(jié)束 for (int j = 1; j<bound; j+) /一趟起泡排序 count1+; /接下來有一次比較 if (rj>rj + 1) /相鄰元素比較 temp = rj; /交換rj和rj+1 rj = rj + 1;rj + 1 = temp;pos = j; /記錄每一次發(fā)生記錄交換的位置當j=0時說明一次比較也沒有了即已經(jīng)全部有序了 count2 = count2 + 3; /一個交換語句為一次移動共移動了次 cout << &q

11、uot;比較" << count1 << "移動" << count2;int Partition(int r, int first, int end, int &count1, int &count2)/快速排序一次劃分 int i = first; /初始化 int j = end;int temp;while (i<j)while (i<j && ri <= rj)j-; /右側(cè)掃描 count1+;if (i<j)temp = ri;ri = rj; /將較小記錄交

12、換到前面 rj = temp;i+;count2 = count2 + 3;count1+;while (i<j && ri <= rj)i+; /左側(cè)掃描 count1+;if (i<j)temp = ri;ri = rj; /將較小記錄交換到前面 rj = temp; /將較大記錄交換到后面 j-;count2 = count2 + 3;count1+;return i; /i為軸值記錄的最終位置 void QuickSort(int r, int first, int end, int &count1, int &count2)/快速排序

13、 if (first<end) /遞歸結(jié)束,繼續(xù)執(zhí)行下邊的操作 int pivot = Partition(r, first, end, count1, count2); /一次劃分 QuickSort(r, first, pivot - 1, count1, count2);/遞歸地對左側(cè)子序列進行快速排序 QuickSort(r, pivot + 1, end, count1, count2); /遞歸地對右側(cè)子序列進行快速排序 void SelectSort(int r, int n)/簡單選擇排序 int i;int j;int index; /初始化 int temp;int

14、count1 = 0, count2 = 0;for (i = 1; i<n; i+) /對n個記錄進行n-1趟簡單選擇排序 index = i; /假設(shè)index是最小的 for (j = i + 1; j<n; j+) /在無序區(qū)中選取最小記錄 if (rj<rindex) /如果該元素比現(xiàn)在第i個位置的元素小 index = j;/賦值給index count1+; /比較次數(shù)加一 /count1+; /在判斷不滿足循環(huán)條件j<n時比較了一次 if (index != i)temp = ri; /將無序區(qū)的最小記錄與第i個位置上的記錄交換 ri = rindex;

15、rindex = temp;count2 = count2 + 3; /移動次數(shù)加 cout << "比較" << count1 << "移動" << count2;void Sift(int r, int k, int m, int &count1, int &count2)/小根堆篩選算法 篩選法調(diào)整堆,st分別為比較和移動次數(shù),m為編號最大的葉子結(jié)點的編號 int i = k;int j = 2 * i + 1; /置i為要篩的結(jié)點j為i的左孩子 int temp;while (j &

16、lt;= m) /篩選還沒有進行到葉子 if (j<m && rj<rj + 1)j+; /比較i的左右孩子j為較大者 count1 = count1 + 2; /該語句之前和之后分別有一次比較 if (ri>rj)break; /根結(jié)點已經(jīng)大于左右孩子中的較大者則結(jié)束循環(huán) elsetemp = ri;ri = rj;rj = temp; /將根結(jié)點與結(jié)點j交換 i = j;j = 2 * i + 1; /下一個被篩結(jié)點位于原來結(jié)點j的位置 count2 = count2 + 3; /移動次數(shù)加 void HeapSort(int r, int n)/堆排序

17、int count1 = 0, count2 = 0; /計數(shù)器計比較和移動次數(shù) int i;int temp;for (i = n / 2; i >= 0; i-) /初始建堆從下向上(從最后一個分支結(jié)點開始)的過程(整體) Sift(r, i, n, count1, count2);for (i = n - 1; i>0; i-) /重復執(zhí)行移走堆頂及重建堆的操作 temp = ri; /將堆頂元素與將堆頂記錄和當前未經(jīng)排序子序列r1.i中最后一個記錄相互交換 ri = r0;r0 = temp; /完成一趟排序輸出記錄的次序狀態(tài) Sift(r, 0, i - 1, count

18、1, count2); /重建堆 cout << "比較" << count1 << "移動" << count2;void Newarray(int a, int b)/產(chǎn)生順序、逆序及隨機數(shù)組 a0 = 0;b0 = 0;for (int s = 1; s<501; s+)as = s; /順序數(shù)組bs = 501 - s; /逆序數(shù)組void main()srand(time(NULL);int c501;c0 = 0;cout << "隨機數(shù)組： "for (i

19、nt s = 1; s < 501; s+)cs = rand() % 50 + 1;cout << cs<<" "const int num = 501; /賦值最大的數(shù)組的容量 int anum;int bnum;int c1num;a0 = 0;b0 = 0; Newarray(a, b);cout << "順序數(shù)組:"for (int j = 1; j<num; j+)cout << aj << " "cout << endl;cout <

20、;< "逆序數(shù)組:"for (int j = 1; j<num; j+)cout << bj << " "cout << endl;cout << endl;cout << "排序方式" << " " << "正序" << " " << "逆序" << " " << "隨機"

21、<<endl<<endl;cout << "直接插入排序" << ""Newarray(a, b);int count1 = 0, count2 = 0;InsertSort(a, num);cout << " "InsertSort(b, num);cout << " "InsertSort(c, num);count1 = 0, count2 = 0;cout << endl<<endl;cout <<

22、"希爾排序" << " "Newarray(a, b);ShellSort(a, num);cout << " "ShellSort(b, num);cout << " "ShellSort(c, num);count1 = 0, count2 = 0;cout << endl<<endl;cout << "起泡排序" << " "Newarray(a, b);BubbleSort(a, nu

23、m);cout << " "BubbleSort(b, num);cout << " "BubbleSort(c, num); count1 = 0, count2 = 0;cout << endl<<endl;cout << "快速排序" << ""Newarray(a, b);QuickSort(a, 0, num - 2, count1, count2);cout << "比較" << count1 << "移動" << count2 << " "count1 = 0, count2 = 0;QuickSort(b, 0, num - 2, count1, co