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

北京郵電大學(xué)信息與通信工程學(xué)院第3頁北京郵電大學(xué)電信工程學(xué)院第1頁數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗四排序（題目1）學(xué)生姓名：班級：班內(nèi)序號：學(xué)號：日期：2013年12月19日1．實驗要求實驗?zāi)康模簩W(xué)習(xí)、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。實驗內(nèi)容：使用簡單數(shù)組實現(xiàn)下面各種排序算法，并進行比較。排序算法：1、插入排序2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序7、其他要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計為3次移動）。3、對2的結(jié)果進行分析，驗證上述各種算法的時間復(fù)雜度。編寫測試main()函數(shù)測試線性表的正確性。2.程序分析2.1存儲結(jié)構(gòu)程序采用的存儲機構(gòu)是順序存儲，如下圖所示：a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]2.2關(guān)鍵算法分析2.2.1插入排序插入排序的基本方法是尋找一個指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C++描述過程如下：①將待插入紀錄賦值給哨兵r[0]：r[0]=r[i];②從后向前進行順序查找：for(j=i-1;r[0]<r[j];j--); ③元素后插：r[j+1]=r[j];④插入記錄：r[j+1]=r[j];性能分析：原序列正序時直接插入排序達到最好的時間性能，比較次數(shù)為n-1，移動次數(shù)為0。原序列逆序時直接插入排序達到最差時間性能，比較次數(shù)為，移動次數(shù)為。 直接插入排序的平均時間復(fù)雜度為，空間復(fù)雜度為。 直接插入排序是一種穩(wěn)定的排序算法，特別適合于待排序集合基本有序的情況。2.2.2希爾排序 希爾排序的基本方法是將待排序的元素集分成多個子集，分別對這些子集進行直接插入排序，待整個序列基本有序時，再對元素進行一次直接插入排序。希爾排序的整個過程如下：for(intd=n/2;d>=1;d=d/2)//以d為增量//在子序列中進行插入排序 { for(inti=d+1;i<=n;i++)//一趟希爾排序 { if(r[i]<r[i-d]) { r[0]=r[i]; for(intj=i-d;j>0&&r[0]<r[j];j=j-d)//每隔d個記錄，進行一次比較和移動，d=1時即是最后一趟直接插入排序 r[j+d]=r[j]; r[j+d]=r[0]; } }}性能分析：希爾排序的時間復(fù)雜度在和之間，空間復(fù)雜度為，是一種不穩(wěn)定的排序算法。2.2.3冒泡排序冒泡排序的基本思想是，兩兩比較相鄰的元素，如果反序，則交換位置，知道沒有反序的元素為止。具體描述如下：//外循環(huán)：總共需要遍歷的趟數(shù)for(inti=1;i<n;i++) {//內(nèi)循環(huán)：每一趟需要比較的次數(shù) for(intj=1;j<=n-i;j++) { if(r[j]>r[j+1])//相鄰元素比較 { r[0]=r[j];r[j]=r[j+1];r[j+1]=r[0]; //若逆序，則交換 } } }性能分析：原序列正序時冒泡排序達到最好的時間性能，比較次數(shù)為n-1，移動次數(shù)為0。原序列逆序時達到最差時間性能，比較次數(shù)為，移動次數(shù)為。平均時間復(fù)雜度為，空間復(fù)雜度為。冒泡排序是一種穩(wěn)定的排序算法。2.2.4快速排序 快速排序是冒泡排序的改進算法，快速排序元素的比較和移動是從兩端向中間進行的，因而元素移動的距離較遠?？焖倥判虻幕舅枷胧?，在分區(qū)中選擇一個元素作為軸值，將待排序元素劃分成兩個分區(qū)，使得左側(cè)元素的關(guān)鍵碼均小于或等于軸值，右側(cè)元素的關(guān)鍵碼均大于或等于軸值，然后分別對這兩個分區(qū)重復(fù)上述過程直到整個序列有序。經(jīng)過優(yōu)化改進的快速排序算法如下：//一趟快速排序intPartion(intr[],intfirst,intend){ inti=first;intj=end; intpivot=r[i];//選取基準(zhǔn)元素 while(i<j) { while((i<j)&&(r[j]>=pivot))//右側(cè)掃描 { j--; } r[i]=r[j]; while((i<j)&&(r[i]<=pivot))//左側(cè)掃描 { i++; } r[j]=r[i]; } r[i]=pivot; returni;}//快速排序voidQSort(intr[],inti,intj){//遞歸直到序列有序 if(i<j) { intpivotloc=Partion(r,i,j); QSort(r,i,pivotloc-1); QSort(r,pivotloc+1,j); }} 性能分析：快速排序的時間復(fù)雜度為，棧的深度為?？焖倥判蚴且环N不穩(wěn)定的排序方法。2.2.5簡單選擇排序 簡單選擇排序的基本思想是：第1趟，在待排序紀錄r[1…n]中選出最小的記錄，將它與r[1]交換；第2趟，在待排序記錄r[2…n]中選出最小的記錄，將它與r[2]交換……以此類推，第i趟將待排序記錄r[i…n]中選出關(guān)鍵碼最小的記錄，與r[i]交換，使有序序列不斷增長直到全部排序完畢。第i趟排序的過程如下：①假設(shè)index是最小的：intindex=i;②查找最小的記錄：for(intj=i+1;j<=n;j++){if(r[j]<r[index])index=j;}③若第一個就是最小元素，則不用交換，否則交換，r[0]為臨時空間：if(index!=i){r[0]=r[i];r[i]=r[index];r[index]=r[0];}性能分析：簡單選擇排序是移動次數(shù)最少的算法，當(dāng)原序列為正序時，比較次數(shù)為，移動次數(shù)為0；當(dāng)原始序列為逆序時，比較次數(shù)為，移動次數(shù)為；平均情況下的時間復(fù)雜度為，空間復(fù)雜度為。簡單選擇排序是不穩(wěn)定的。2.2.6堆排序堆排序采用堆的存儲結(jié)構(gòu)，即將數(shù)組r[]存在一個二叉樹中，根節(jié)點存放在r[1]，假設(shè)某結(jié)點存放在r[i]，則其左孩子存放在r[2i]，右孩子存放在r[2i+1]，非根結(jié)點r[i]的雙親結(jié)點存放在r[n/2]。每個結(jié)點的值都不大于其左右孩子結(jié)點的值的堆叫做小根堆，大根堆同里定義。采用小根堆存儲的堆排序的基本思想為小根堆的篩選過程，即：總是將根結(jié)點與左右孩子結(jié)點進行比較，若不滿足小根堆條件，則將根結(jié)點與較小的結(jié)點交換，一直到葉子結(jié)點，或所有子樹均為小根堆為止。小根堆的篩選算法如下：voidSift(intr[],intk,intm)//m為編號最大的葉子結(jié)點的編號{ inti=k,j=2*i;//i是要篩選的結(jié)點，j是i的左孩子 while(j<=m) { if(j<m&&r[j]>r[j+1])//j是左右孩子中較小者 j++; if(r[i]<r[j])break;//符合小根堆的條件，結(jié)束 else { r[0]=r[i]; r[i]=r[j]; r[j]=r[0]; i=j;j=2*i; } }}堆排序的具體過程為：①將待排序的元素構(gòu)造成一個堆；②輸出堆頂元素；③將堆中最后一個元素移至堆頂，并將剩余元素調(diào)整成堆。反復(fù)執(zhí)行②和③直到堆中只有一個元素，代碼如下：voidHeapSort(intr[],intn){ for(inti=n/2;i>=1;i--)//建堆 Sift(r,i,n); for(inti=1;i<n;i++)//輸出堆頂元素，重新建堆 { r[0]=r[1]; r[1]=r[n-i+1]; r[n-i+1]=r[0]; Sift(r,1,n-i); }}使用小根堆的算法時，排序結(jié)束后從r[1]到r[n]是逆序的。性能分析：堆排序可初始建堆的時間復(fù)雜度為，第i次建堆的時間復(fù)雜度為，一共n-i次輸出堆頂元素，總的時間復(fù)雜度為。堆排序是不穩(wěn)定的排序算法。2.3性能比較排序方法平均時間復(fù)雜度輔助空間穩(wěn)定性直接插入排序穩(wěn)定希爾排序~不穩(wěn)定冒泡排序穩(wěn)定快速排序~不穩(wěn)定簡單選擇排序不穩(wěn)定堆排序穩(wěn)定3.程序運行結(jié)果測試主函數(shù)流程：開開始構(gòu)造正序、逆序、隨機序列構(gòu)造正序、逆序、隨機序列對正序序列使用七種排序方法對逆序序列使用七種排序方法對隨機序列使用七種排序方法結(jié)束結(jié)束測試條件：編譯環(huán)境為MicrosoftVisualStudio2010Ultimate