一、概念
資料排序 ：排序就是將一組物件按照規定的次序重新排列的程序，排序往往是為檢索服務的，
穩定排序 ：若排序后，相同關鍵字的記錄保持它們原來的相對次序，則此排序方法稱為穩定排序；穩定性是排序方法本身的特性，與資料無關，
排序型別：
- 內部排序： 全部資料存于記憶體；
- 外部排序: 需要對外存進行訪問的排序程序
排序指標（排序演算法性能分析）：
- 存盤空間
- 比較次數
二、插入排序
常用的插入排序方法有直接插入排序、折半插入排序、表插入排序和希爾排序，
直接插入排序(Straight Insertion Sorting)是一種簡單的排序方法，它的基本思想是依次將每個記錄插入到一個已排好序的有序表中去，從而得到一個新的、記錄數增加 1 的有序表，直接插入排序類似圖書館中整理圖書的程序，
// R 待排序的表 n是表長 void StraightlnsertSort(List R,int n){ int i,j; for (i=2;i<=n;i++){ R[0]=R[i];//第 i 個記錄復制為崗哨 j=i-1; while (R[0].key<R[j].key){ //與崗哨比較，直至鍵值不大于崗哨鍵值 R[j+1]=R[j]; //將第 j 個記錄賦值給第 j+1 個記錄 j--; } R[j+1]=R[0]; //將第 i 個記錄插入到序列中 } }
記錄 R[0]有兩個作用，其一是進入查找回圈之前，它保存了 R[i]的值，使得不致于因 記錄的后移而丟失 R[i]中的內容；其二是起崗哨作用，在 while 回圈中“監視”陣列下標 變數 j 是否越界，一旦越界(即 j<1), R[0]自動控制 while 回圈的結束，從而避免了在 while 回圈中每一次都要檢測 j 是否越界，這一技巧的應用，使得測驗回圈條件的時間大 約減少一半，
演算法分析：直接插入排序的演算法簡單，易于理解，容易實作，時間復雜度為 O(n2 )，若待排序記錄 的數量很大時，一般不選用直接插入排序，從空間來看，它只需要一個記錄的輔助空間，即 空間復雜度為 O(1)， 直接插入排序方法是穩定的，
●存盤空間 n+1；（1為附加空間），空間復雜度 O(1）
●時間復雜度 O(n^ 2) ，如果給出的待排序表是順序的，則時間復雜度最好 O(n)
●穩定性：穩定排序；
三、交換排序
交換排序的基本思想：比較兩個記錄鍵值的大小，如果這兩個記錄鍵值的大小出現逆 序，則交換這兩個記錄，這樣將鍵值較小的記錄向序列前部移動，鍵值較大的記錄向序列 后部移動，
交換排序包括：冒泡排序和快速排序，
1、冒泡排序：
基本思想： 通過多次重復比較、交換相鄰記錄而實作排序；每一趟的效果都是將當前鍵值最大的記錄換到最后
在演算法實作時，定義一個整型變數 endsort，在每一次排序之前，先將它置為 0，若 在一趟起泡中交換了記錄，則將它置為 1，當一次回圈結束時，我們再檢查 endsort，若 endsort 的值為 0 便終止演算法，
// R 待排序的表 n是表長 void BubbleSort(List R,int n){ /*endsort:標志檔案是否已排好序*/ for( i=1; i<=n-1; i++ ){ endsort=0; /*若回圈中記錄未作交換,則說明序列已有序*/ for( j=1; j<=n-i-1; j++ ){ if( R[j].key > R[j+1].key ){ temp=R[j]; R[j]=R[j+1]; R[j+1]=temp; endsort=1； } } if(endsort==0) break; } }
- 時間復雜度： O(n2 ) 、如果是排好序的表 O(n)
- 空間復雜度 ：O(1)
- 穩定性：穩定排序，
2、快速排序(Quick Sorting)是交換排序的一種，實質上是對冒泡排序的一種改進；首先取第一個記錄，將之與表中其余記錄比較并交換，從而將它放到記錄的正確的最終位置，使記錄表分成兩部分{其一（左邊的）諸記錄的關鍵字均小于它；其二（右邊的）諸記錄的關鍵字均大于它}；然后對這兩部分重新執行上述程序，依此類推，直至排序完畢
四、選擇排序
選擇排序(Selection Sorting)的基本思想：每一次在 n-i+1(i=1，2,…，n-1)個記錄中 選取鍵值最小的記錄作為有序序列的第 i 個記錄，
分類：直接選擇排序和堆排序
1.直接選擇排序
直接選擇排序演算法的基本思想：在第 i 次選擇操作中，通過 n-i 次鍵值間比較，從 n-i+1個記錄中選出鍵值最小的記錄，并和第 i(1≤i≤n-l)個記錄交換，
void SelectSort (List R,int n){ int min,i,j; //每次回圈，選擇出一個最小鍵值 for(i=1;i<=n-1;i++){ min=i; //假設第 i 個記錄鍵值最小 for (j=i+1;j<=n;j++){ if (R[j].key<R[min].key){ min=j;//記錄下鍵值較小記錄的下標 }
}； if (min!=i){ swap(R[min],R[i]); //將最小鍵值記錄和交換第 i 個記錄交換 } } }
2、堆排序
建堆（篩選法）：
- 1）方法：
- 設記錄{ R 1 , R 2 , …., R n }
- (1)順序輸入成完全二叉樹（以陣列存盤）
- (2)從最后一個雙親開始，如果有較小的孩子，則將其沿左或右孩中小的那個方向篩下，一直到不能再篩；
- (3)逐次處理完每個雙親，
對排序的特點：
- 在堆排序中，對于 n 個記錄進行序所需的平均時間是 O(nlog2n)，
- 在最壞情況下，其 時間復雜度也為 O(nlog2n)，
- 相對于快速排序來說，這是堆排序的最大優點，
- 堆排序 僅需一個記錄大小的供交換用的輔助存盤空間，O(1)
- 堆排序是不穩定的，
五、歸并排序
歸并排序(Merge Sorting)是與插入排序、交換排序、選擇排序不同的一類排序方法，其不 同之處在于要求待排序列是由若干個有序子序列組成，歸并的含義是將兩個或兩個以上的有 序表合并成一個新的有序表，合并的方法是比較各子序列的第一個記錄的鍵值，最小的一個 就是排序后序列的第一個記錄的鍵值，取出這個記錄，繼續比較各子序列現有的第一個記錄 的鍵值，便可找出排岸后的第二個記錄，如此繼續下去，最終可以得到排序結果， 因此歸并排序的基礎是合并，
分類：
- 有序序列的合并
- 二路歸并排序
歸并排序演算法的時間復雜度為 O(nlog2n)，由于要用到和待排記錄等數量的陣列 b 來存放結 果，所以實作歸并排序需要附加一倍的存盤開銷，二路歸并排序是穩定的，在 n 較大時，歸并排序的時間性能優于堆排序，但它所需的輔助存盤量較多，O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65489.html
標籤：其他
上一篇：詳細分析動態陣列的資料結構的實作程序（Java 實作）
下一篇：PAT B# 1025 反轉鏈表