C語言內(nèi)排序法實驗報告.doc

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