數(shù)據(jù)結(jié)構(gòu)內(nèi)部排序比較

1、數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報(bào)告實(shí)驗(yàn)名稱：數(shù)據(jù)結(jié)構(gòu)題目：內(nèi)部排序比較專業(yè)： 班級(jí)： 姓名： 學(xué)號(hào)： 實(shí)驗(yàn)日期：一、實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)隨機(jī)數(shù)據(jù)比較各內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)的次數(shù)，以取得直觀感受。訓(xùn)練學(xué)生綜合設(shè)計(jì)算法能力。二、實(shí)驗(yàn)要求：待排序長(zhǎng)度不小于100，數(shù)據(jù)可有隨機(jī)函數(shù)產(chǎn)生，用五組不同輸入數(shù)據(jù)做比較，比較的指標(biāo)為關(guān)鍵字參加比較的次數(shù)和關(guān)鍵字移動(dòng)的次數(shù)；對(duì)結(jié)果做簡(jiǎn)單的分析，包括各組數(shù)據(jù)得出結(jié)果的解釋；設(shè)計(jì)程序用順序存儲(chǔ)。三、實(shí)驗(yàn)內(nèi)容1、待排序表的表長(zhǎng)不小于100；至少要用5組不同的輸入數(shù)據(jù)作比較；排序算法不少于3種；2 、待排序的元素的關(guān)鍵字為整數(shù)；3 、比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵

2、字的移動(dòng)次數(shù)(關(guān)鍵字交換以3次計(jì))。4、演示程序以人機(jī)對(duì)話的形式進(jìn)行。每次測(cè)試完畢顯示各種比較指標(biāo)的列表，以便比較各種排序的優(yōu)劣。5、最后要對(duì)結(jié)果作簡(jiǎn)單的分析。6、測(cè)試數(shù)據(jù)：用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生。四、實(shí)驗(yàn)編程結(jié)果或過(guò)程：1. 數(shù)據(jù)定義typedef struct KeyType key;RedType;typedef struct RedType rMAXSIZE+1;int length;SqList;2. 函數(shù)如下，代碼詳見文件“排序比較.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)/冒泡排序void In

3、sertSort(SqList &L)/插入排序 void SelectSort(SqList &L) /簡(jiǎn)單選擇排序int Partition(SqList &L,int low,int high)void QSort(SqList &L,int low,int high)/遞歸形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)/希爾排序 void ShellSort(SqList &L,int dlta )3. 運(yùn)行測(cè)試結(jié)果，運(yùn)行結(jié)果無(wú)誤，如下圖語(yǔ)速

4、個(gè)數(shù)為20元素個(gè)數(shù)為100錯(cuò)誤調(diào)試 無(wú)。影響排序的因素：1、待排序的記錄數(shù)目n 的大小。2、記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大小。3、關(guān)鍵字的結(jié)構(gòu)及其分布情況。4、對(duì)排序穩(wěn)定性的要求五、實(shí)驗(yàn)總結(jié)：（1）實(shí)驗(yàn)中的存在問(wèn)題和提高1、存在問(wèn)題：程序有待增強(qiáng)。2、提高：界面處理簡(jiǎn)潔。（2）收獲與體會(huì)：1、隨機(jī)數(shù)的生成；2、排序的算法的比較次數(shù)與移動(dòng)次數(shù)的計(jì)算3、各種排序的算法附錄 源程序/*一.選擇排序算法：算法基本原理：一次選定數(shù)組中的每一個(gè)數(shù)，記下當(dāng)前位置并假設(shè)它是從當(dāng)前位置開始后面數(shù)中的最小數(shù)min=i，從這個(gè)數(shù)的下一個(gè)數(shù)開始掃描直到最后一個(gè)數(shù)，并記錄下最小數(shù)的位置mi

5、n，掃描結(jié)束后如果min不等于i，說(shuō)明假設(shè)錯(cuò)誤，否則交換min與i位置上數(shù)。算法實(shí)現(xiàn)：*/#include <stdio.h>/選擇排序，如果第一個(gè)數(shù)字小于后面的則向后移動(dòng)，依次類推/該排序時(shí)不穩(wěn)定的，時(shí)間復(fù)雜度是N平方int main()int array10 = 112,4,2,3,5,33,6,7,8,9;/定義一個(gè)數(shù)組int length = sizeof(array)/sizeof(array0);/得到數(shù)組的長(zhǎng)度int min, k=0, s=0, i=0, j=0;/k保存臨時(shí)結(jié)果，s，i，j為循環(huán)變量/選擇排序開始for(i=0;i<length;i+) mi

6、n=i; for(j=i+1;j<length;j+) if(arrayi>arrayj) min=j; if(min!=i) k=arrayi; arrayi=arrayj; arrayj=k; /選擇排序結(jié)束，輸出顯示排序的結(jié)果for(s=0; s<length; s+)printf("%d n",arrays);return 0; /*二.冒泡排序算法基本原理：對(duì)尚未排序的各元素從頭到尾依次比較相鄰的兩個(gè)元素是否逆序（與欲排順序相反），若逆序就交換這兩元素，經(jīng)過(guò)第一輪比較排序后便可把最大（或最?。┑脑嘏藕?，然后再用同樣的方法把剩下的元素逐個(gè)進(jìn)行比較

7、，就得到了你所要的順序。算法實(shí)現(xiàn)：*/#include <stdio.h>/冒泡排序,開始的時(shí)候兩個(gè)數(shù)進(jìn)行比較，大的向后小的向前，第一次比較很容易的就把最大的一個(gè)數(shù)字放到了最后小的呢，繼續(xù)向前，第二次當(dāng)然也找到了第二個(gè)大的，放到倒數(shù)第二的位置，如此下去便可。這個(gè)是優(yōu)化的冒泡排序方法，讓k=j保存最后的那個(gè)數(shù)的下標(biāo)，這樣k后面的數(shù)都是排序好的了,這個(gè)排序是穩(wěn)定的，時(shí)間復(fù)雜度是N平方int main()int array10 = 1,2,11,22,33,4,23,234,4,6;int length = sizeof(array)/sizeof(array0);int k=0, s=

8、0, i=0, j=0, m=0;/冒泡排序開始for(i = length-1;i>0;i=k)for(j=0, k=0;j<i;j+)if(arrayj>arrayj+1)/把比較出來(lái)大的數(shù)據(jù)向后移動(dòng)m=arrayj;arrayj=arrayj+1;arrayj+1=m;k=j;/冒泡排序結(jié)束，輸出顯示排序的結(jié)果for(s=0; s<length; s+)printf("%d n",arrays);return 0;/*三.快速排序算法基本原理：快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。

9、它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。算法實(shí)現(xiàn)：*/#include <stdio.h>/快速排序開始，使用遞歸方法，取其中一個(gè)數(shù)（任意基本上都是以第一個(gè)為準(zhǔn)），先從后面比較，如果這個(gè)數(shù)比后面的大交換之，如果不大繼續(xù)比較直到大為止，如果大，則交換之，再到前面比較，如果前面的比這個(gè)數(shù)小交換之再和后面的比較，第一趟下來(lái)比它小的就在前面了，比它大的就在后面嘍，然后再把該數(shù)組分成兩部分使用遞歸，直到最后排序完成vo

10、id paixu(int array, int low, int hight)int i,j,t,m;if(low<hight)i = low;j = hight;t = arraylow;while(i<j)while(i<j && arrayj>t)/開始和后面的比較，如果后面的比他大繼續(xù)，如果后面的比它小交換之j-;if(i<j)/在沒(méi)有越界（i是從前面開始，j是從后面開始）的情況下進(jìn)行交換m=arrayi;arrayi=arrayj;arrayj=m;i+;/讓前面的向后移動(dòng)一個(gè)繼續(xù)比較while(i<j && arr

11、ayi<=t)/和前面的比較，如果前面的小于等于該關(guān)鍵數(shù)據(jù)繼續(xù)，如果大于交換之i+;if(i<j)m=arrayj;arrayj=arrayi;arrayi=m;j-;arrayi=t;/第一次比較結(jié)束，把i放到中間的位置，也即在i前面都比i小，在i后面都比i大paixu(array, low, i-1);/前面部分實(shí)現(xiàn)遞歸paixu(array, i+1, hight);/后面部分實(shí)現(xiàn)遞歸int main()int s=0;int array = 10,22,3,21,45,67,2,11,110,453;int length = sizeof(array)/sizeof(arr

12、ay0);paixu(array,s,length-1);for(s=0;s<length;s+)printf("%d n",arrays);return 0; /*四.插入排序概述：有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為()。是穩(wěn)定的排序方法。插入算法（insertion sort）把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)

13、數(shù)組的所有元素，但將最后一個(gè)元素除外，而第二部分就只包含這一個(gè)元素。在第一部分排序后，再把這個(gè)最后元素插入到此刻已是有序的第一部分里的正確位置中。包括：直接插入排序，折半插入排序，鏈表插入排序，Shell排序算法基本原理：假定這個(gè)數(shù)組的序是排好的,然后從頭往后,如果有數(shù)比當(dāng)前外層元素的值大,則將這個(gè)數(shù)的位置往后挪,直到當(dāng)前外層元素的值大于或等于它前面的位置為止.這具算法在排完前k個(gè)數(shù)之后,可以保證a1k是局部有序的,保證了插入過(guò)程的正確性.算法描述：一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序2. 取出下一個(gè)元素，在已

14、經(jīng)排序的元素序列中從后向前掃描3. 如果該元素（已排序）大于新元素，將該元素移到下一位置4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置5. 將新元素插入到該位置中6. 重復(fù)步驟2如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來(lái)減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。 算法實(shí)現(xiàn)：*/#include <stdio.h>int main()int array = 9,43,567,1,45,23,123,54,234,987;int length = sizeof(array)/sizeof(array0);int i,j,t,

15、m;/插入排序開始for(i=1;i<length;i+)/默認(rèn)下標(biāo)為0的已經(jīng)是排序好的，所以從1開始t = arrayi;j=i;while(j>0)&&(arrayj-1>t)/如果前面的數(shù)比它大交換之m=arrayj-1;arrayj-1=arrayj;arrayj=m;j-;/交換完畢繼續(xù)比較/插入排序結(jié)束for(i=0;i<length;i+)printf("%d n",arrayi);return 0; /*五.希爾排序希爾排序是基于插入排序的一種算法，在此算法基礎(chǔ)之上增加了一個(gè)新的特性，提高了效率。希爾排序的時(shí)間復(fù)雜度為

16、 O(N*(logN)2)， 沒(méi)有快速排序算法快 O(N*(logN)，因此中等大小規(guī)模表現(xiàn)良好，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O(N2）復(fù)雜度的算法快得多。并且希爾排序非常容易實(shí)現(xiàn)，算法代碼短而簡(jiǎn)單。此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時(shí)快速排序在最壞的情況下執(zhí)行的效率會(huì)非常差。專家門提倡，幾乎任何排序工作在開始時(shí)都可以用希爾排序，若在實(shí)際使用中證明它不夠快，再改成快速排序這樣更高級(jí)的排序算法. 本質(zhì)上講，希爾排序算法的一種改進(jìn)，減少了其復(fù)制的次數(shù)，速度要快很多。原因是，當(dāng)N值很大時(shí)數(shù)據(jù)項(xiàng)每一趟排序需要的個(gè)數(shù)很少，但數(shù)據(jù)項(xiàng)的距離很長(zhǎng)。當(dāng)N值減小時(shí)每

17、一趟需要和動(dòng)的數(shù)據(jù)增多，此時(shí)已經(jīng)接近于它們排序后的最終位置。正是這兩種情況的結(jié)合才使希爾排序效率比插入排序高很多。 在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對(duì)插入下一個(gè)數(shù)沒(méi)有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過(guò)多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。下面的函數(shù)是一個(gè)希爾排序算法的一個(gè)實(shí)現(xiàn)，初次取序列的一半為增量，以后每次減半，直到增量為1。希爾排序是不穩(wěn)定的。 算法實(shí)現(xiàn)：*/#include <stdio.h>int main()int array = 1,445,754,77,35,123,754,876,54,3;int length = sizeof