C語言內(nèi)排序法實(shí)驗(yàn)報(bào)告.doc

數(shù)據(jù)結(jié)構(gòu)一：排序方法比較1、冒泡排序?qū)儆诜€(wěn)定排序，是一種借助“交換”進(jìn)行排序的方法。首先要將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄與第三個(gè)記錄的關(guān)鍵字，以此類推，直至第n-1個(gè)記錄與第n個(gè)記錄的關(guān)鍵字進(jìn)行比較為止，這一過程稱為第一趟冒泡排序，其結(jié)果使得關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄的位置上；然后進(jìn)行第二趟冒泡排序，對(duì)前N-1個(gè)記錄進(jìn)行同樣操作；以此類推，直到在一趟排序過程中沒有進(jìn)行過交換記錄的操作為止。2、直接插入排序?qū)儆诜€(wěn)定的排序，每次從無序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程，結(jié)束該次循環(huán)。3、快速排序?qū)儆诓环€(wěn)定排序，是對(duì)起泡排序的一種改進(jìn)。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。假設(shè)待排序的序列為R.s,R.s+1,.,R.t,首先任意選取一個(gè)記錄，然后按下述原則從新排序記錄：將關(guān)鍵字較他小的記錄都安置在他的位置之前，將所有關(guān)鍵字較他大的記錄都安置在他的位置后面。由此可以該“樞軸”記錄最后所落的位置i作為分界線，將序列Rs,Rs+1.Rt分割成兩個(gè)子序列Rs,Rs+1.Ri-1和Ri+1Rt，這個(gè)過程稱作一趟快速排序。一趟快速排序的具體做法是：附設(shè)兩個(gè)指針low和high，它們的初值分別指向數(shù)組第一個(gè)數(shù)據(jù)和最后一個(gè)數(shù)據(jù)，將樞軸記錄暫存在R0的位置上排序過程中只作Rlow或Rhigh的單向移動(dòng)，直至一趟排序結(jié)束后再將樞軸記錄移至正確位置上。4、簡(jiǎn)單選擇排序?qū)儆诓环€(wěn)定排序，基本思想是，每一趟在n-i+1（i=1，2，n-1）個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。第i趟簡(jiǎn)單選擇排序是指通過n-i次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄進(jìn)行交換。共需進(jìn)行n-1趟比較，直到所有記錄排序完成為止。例如：進(jìn)行第i趟選擇時(shí)，從當(dāng)前候選記錄中選出關(guān)鍵字最小的k號(hào)記錄，并和第i個(gè)記錄進(jìn)行交換。5、希爾排序?qū)儆诓环€(wěn)定排序，也是一種屬插入排序類，它的基本思想是：先將整個(gè)待排記錄序列分割稱為若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。希爾排序的一個(gè)特點(diǎn)是：子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。6、二叉樹排序?qū)儆诓环€(wěn)定排序，它的基本思想是，先將初始文件R1.n建成一個(gè)大根堆，此堆為初始的無序區(qū)，再將關(guān)鍵字最大的記錄R1(即堆頂)和無序區(qū)的最后一個(gè)記錄Rn交換，由此得到新的無序區(qū)R1.n-1和有序區(qū)Rn，且滿足R1.n-1.keysRn.key；由于交換后新的根R1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R1.n-1調(diào)整為堆，然后再次將R1.n-1中關(guān)鍵字最大的記錄R1和該區(qū)間的最后一個(gè)記錄Rn-1交換，由此得到新的無序區(qū)R1.n-2和有序區(qū)Rn-1.n，且仍滿足關(guān)系R1.n- 2.keysRn-1.n.keys，同樣要將R1.n-2調(diào)整為堆。直到無序區(qū)只有一個(gè)元素為止。輸入待排序列Rn+1選擇排序類型sortSort直接插入冒泡排序快速排序簡(jiǎn)單選擇希爾排序輸出結(jié)果結(jié)束二叉樹排序開始二：程序流程圖：三：實(shí)驗(yàn)總結(jié)：本實(shí)驗(yàn)綜合了多種內(nèi)排序方法，深入了解了其算法，并將6種內(nèi)排序方法綜合起來做了比較，對(duì)于這6種算法也更加了解，知道各自有何不同，各自適合哪種情況，雖然本次實(shí)驗(yàn)比較和程序段有很多都