排序演算法比較分析
專業班級：08軟體工程2班
姓名： 汪偉
學號： 08010***xx
設計時間： 2010-9-15—-2010-9-27
指導教師： 楊薇薇
課程設計報告的內容
一、題目：排序演算法比較
1、 設計目的
1． 掌握各種排序的基本思想。
2． 掌握各種排序方法的演算法實現。
3． 掌握各種排序方法的優劣分析及花費的時間的計算。
4． 掌握各種排序方法所適應的不同場合。
2、 設計內容和要求
利用隨機函式產生30000個隨機整數，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸併排序等排序方法進行排序，並統計每一種排序上機所花費的時間
二、 執行環境（軟、硬體環境）
軟體環境：vc6.0程式設計軟體
執行平台： win32
硬體： 普通個人pc機
三、 演算法設計的思想
1、氣泡排序：bubblesort()
基本思想: 設待排序的檔案為r[1..n]
第1趟(遍)：從r[1]開始,依次比較兩個相鄰記錄的關鍵字
r[i].key和r[i+1].key,若r[i].key>r[i+1].key，則交換記錄
r[i]和r[i+1]的位置；否則,不交換。
(i=1,2,...n-1)
第1趟之後,n個關鍵字中最大的記錄移到了r[n]的位置上。
第2趟：從r[1]開始,依次比較兩個相鄰記錄的關鍵字
r[i].key和r[i+1].key,若r[i].key>r[i+1].key，則交換記錄
r[i]和r[i+1]的位置；否則,不交換。
(i=1,2,...n-2)
第2趟之後,前n-1個關鍵字中最大的記錄移到了r[n-1]的位
置上，作完n-1趟,或者不需再交換記錄時為止。
2、選擇排序：selsort()
每一趟從待排序的資料元素中選出最小（或最大）的乙個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。
選擇排序不像氣泡排序演算法那樣先並不急於調換位置，第一輪（k=1）先從array[k]開始逐個檢查，看哪個數最小就記下該數所在的位置於minlindex中，等一輪掃瞄完畢，如果找到比array[k-1]更小的元素，則把array[minlindex]和a[k-1]對調，這時array[k]到最後乙個元素中最小的元素就換到了array[k-1]的位置。 如此反覆進行第二輪、第三輪…直到迴圈至最後一元素
3、直接插入排序 ：inssort()
在已經排好序的序列中查詢待插入的元素的插入位置，並將待插入元素插入到有序列表中的過程。
將陣列分成兩部分，初始化時，前部分陣列為只有第乙個元素，用來儲存已排序元素，我們這裡叫 arr1 ；後部分陣列的元素為除第乙個元素的所有元素，為待排序或待插入元素，我們這裡叫 arr2 。
排序時使用二層迴圈：第一層對 arr2 進行迴圈，每次取後部分陣列（待排序陣列）裡的第乙個元素（我們稱為待排序元素或稱待插入元素） e1 ，然後在第二層迴圈中對 arr1 （已排好序的陣列）從第乙個元素往後進行迴圈，查到第乙個大於待插入元素（如果是公升序排列）或第乙個小於待插入元素（如果是降序排列） e2 ，然後對 arr1 從 e2 元素開始往後的所有元素向後移，最後把 e1 插入到原來 e2 所在的位置。這樣反覆地對 arr2 進行迴圈，直到 arr2 中所有的待插入的元素都插入到 arr1 中。
4、快序排序：quicksort()
基本思想：首先在r[1..n]中，確定乙個r[i]，經過比較和
移動，將r[i]放到"中間"某個位置上，使得r[i]左邊所有記錄
的關鍵字小於等於r[i].key，r[i]右邊所有記錄的關鍵字大於等
於r[i].key。以r[i]為界,將檔案劃分為左、右兩個子檔案。
用同樣的方法分別對這兩個子檔案進行劃分, 得到4個更小
的子檔案。繼續進行下去,使得每個子檔案只有乙個記錄為止,
便得到原檔案的有序檔案。
例. 給定檔案(20,05,37,08,63,12,59,15,44,08)，選
用第1個元素20進行劃分:
5、歸併排序：megesort()
假定檔案(r[1],r[2],...,r[n])中記錄是隨機排列的,進行
2-路歸併排序，首先把它劃分為長度均為1的n個有序子檔案，
然後對它們逐步進行2－路歸併排序。其步驟如下：
第1趟：從r[1..n]中的第1個和第2個有序子檔案開始,呼叫
演算法merge,每次歸併兩個相鄰子檔案,歸併結果放到y[1..n]中。
在y中形成 n/2 個長度為2的有序子檔案。若n為奇數,則y中最
後乙個子檔案的長度為1。
第2趟：把y[1..n]看作輸入檔案,將 n/2 個有序子檔案兩
兩歸併,歸併結果回送到r[1..n]中,在r中形成 n/2 /2 個長度為4的有序子檔案。若y中有奇數個子檔案，則r中最後乙個子文
件的長度為2。
共計經過 log2n 趟歸併,最後得到n個記錄的有序檔案。
6、堆排序：heapsort()
堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
1、n（n>1）個節點的的完全二叉樹從層次從左自右編號，最後乙個分枝節點（非葉子節點）的編號為 n/2 取整。2、且對於編號 i（1<=i<=n）有：父節點為 i/2 向下取整；若2i>n，則節點i沒有左孩子，否則其左孩子為2i；若2i+1>n，則沒有右孩子，否則其右孩子為2i+1。
3、這裡使用完全二叉樹只是為了好描述演算法，它只是一種邏輯結構，真真在實現時我們還是使用陣列來儲存這棵二叉樹的，因為完全二叉樹完全可以使用陣列來儲存。
堆排序其實最主要的兩個過程：第一步，建立初始堆；第二步，交換根節點與最後乙個非葉子節
從最後乙個非葉子節點為開始向前迴圈每個會支節點，比較每個分支節點與他左右子節點，如果其中某個子節點比父節點大，則與父節點交換，交換後原父節點可能還小於原子節點的子節點，所以還需對原父節點進行調整，使用原父節點繼續下沉，直到沒有子節點或比左右子節點都大為止，呼叫過程可通過遞迴完成。當某個非葉子節點調整完畢後，再處理下乙個非葉子節點，直到根節點也調整完成，這裡初始堆就建立好了，這裡我們建立的是大頂堆，即大的元素向樹的根浮，這樣排序最後得到的結果為公升序，因為最大的
將樹中的最後乙個元素與堆頂元素進行交換，並從樹中去掉最後葉子節點。交換後再按建立初始堆的演算法調整根節點，如此下去直到樹中只有乙個節點為止。
四、 演算法的流程圖
五、 演算法設計分析
1、氣泡排序：bubblesort()
氣泡排序演算法分析：
(1)最好情況, 待排序的檔案已是有序檔案:
只需要進行1趟排序,
共計比較關鍵字的次數為n－1
不交換記錄。
(2)最壞情況, 要經過n-1趟排序，
所需總的比較關鍵字的次數為
(n-1)+(n-2)+...+1＝n(n-1)/2
交換記錄的次數最多為
(n-1)+(n-2)+...+1＝n(n-1)/2
移動記錄次數最多為
3n(n-1)/2
(3)只需要少量中間變數作為輔助空間。
演算法是穩定的。
2、選擇排序：selsort()
選擇排序演算法分析：
(1)比較次數，在任何情況下,均為
(2)交換記錄的次數
在最好情況下,原n個記錄遞增有序：不移動記錄。
在最壞情況下共交換記錄n-1對,移動記錄數3(n-1)次。
故,時間複雜度為o(n2)。
(3)只需少量中間變數作為輔助空間。
(4)演算法是不穩定的。
3、直接插入排序 ：inssort()
直接插入排序演算法分析：
故,時間複雜度為o(n2)。
(4) 只需少量中間變數作為輔助空間。
(5) 演算法是穩定的。
4、快序排序：quicksort(d)
快速排序演算法分析：
(1)就平均速度而言，
快速排序是已知內部排序方法中最好的一種排序方法,
其時間複雜度為
o(nlog(n))。
(2)在最壞情況下，
快速排序所需的比較次數和氣泡排序的比較次數相同,
其時間複雜度為
o(n2)。
(3)快速排序需要乙個棧作輔助空間，用來實現遞迴處理左、右子檔案。
在最壞情況下,遞迴深度為n，
所需棧的空間大小為
o(n)。
(4)快速排序是不穩定的。
5、歸併排序：megersort()
歸併排序演算法分析：
(1)對n個記錄的檔案進行歸併排序,共需
log2n 趟,
(2)每趟所需比較關鍵字的次數不超過n, 共比較
o(nlog2n) 次。
(3)每趟移動n個記錄, 共移動記錄
o(nlog2n) 個
(4)歸併排序需要乙個大小為n的輔助空間
y[1..n]。
(5)歸併排序是穩定的。
6、堆排序：heapsort()
堆排序演算法分析：
(1)堆排序的時間，主要由建立初始堆和反覆重建堆這兩部分的時間開銷構成，
它們均是通過呼叫heapify實現的。
(2)堆排序的最壞時間複雜度為
o(nlgn)。
(3)堆排序的平均效能較接近於最壞效能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的檔案。
(4)堆排序是就地排序，輔助空間為
o(1)。
(5)它是不穩定的排序方法
六、 源**
#include
#include
#include
#include
#include
//外部變數定義
int count1=0,bj1=0,yd1=0;
int count2=0,bj2=0,yd2=0;
int count3=0,bj3=0,yd3=0;
int count4=0,bj4=0,yd4=0;
int count5=0,bj5=0,yd5=0;
int count6=0,bj6=0,yd6=0;
clock_t start1,finish1;
clock_t start2,finish2;
clock_t start3,finish3;
clock_t start4,finish4;
資料結構課程設計實驗報告
姓名 陳白楊 班級 軟092 老師 王森玉 學號 099074177 實驗一 農夫過河問題 1 題目 農夫過河問題 2 問題描述 從前，一人農夫帶著乙隻狼，乙隻羊和一棵白菜 注意該狼已被農夫馴服了，但還是會吃羊 他要將所有東西安全的帶到河的對岸。不幸的是河邊只有一條小船，只能裝下農夫和他的一樣東西，...
資料結構課程設計心得
篇一 資料結構課程設計心得體會 通過本次課程設計，對圖的概念有了乙個新的認識，在學習離散數學的時候，總覺得圖是很抽象的東西，但是在學習了 資料結構與演算法 這門課程之後，我慢慢地體會到了其中的奧妙，圖能夠在計算機中存在，首先要捕捉他有哪些具體化 數位化的資訊，比如說權值 頂點個數等，這也就說明了想要...
資料結構課程設計報告
交通諮詢系統設計 不用輸入程式語句，也不用那個截圖 不用太著急，報告周五之前給我就行了 列印和壓縮包都要哈！對了，這段文字記得刪掉啊嘿嘿 題目名稱交通諮詢系統設計 院 系 管理學院 課程名稱資料結構課程設計 班級資訊 10 2 學生姓名呂德麗 指導教師李長雲 目錄一 需求分析及選題要求 3 1 問題...