|
?
排序算法分析
1．排序算法的基本操作
??? 大多數排序算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
? 注意：
??? 第(2)種基本操作的實現依賴于待排序記錄的存儲方式。
2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
??? 排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）
（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；
（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用于難于在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。
3．排序算法性能評價
（1） 評價排序算法好壞的標準
評價排序算法好壞的標準主要有兩條：
??? ① 執行時間和所需的輔助空間
??? ② 算法本身的復雜程度
（2） 排序算法的空間復雜度
若排序算法所需的輔助空間并不依賴于問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。
（3） 排序算法的時間開銷
大多數排序算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序算法其執行時間不僅依賴于問題的規模，還取決于輸入實例中數據的狀態。
文件的順序存儲結構表示
? #define n l00 //假設的文件長度，即待排序的記錄數目
? typedef int KeyType； //假設的關鍵字類型
? typedef struct{ //記錄類型
??? KeyType key； //關鍵字項
??? InfoType otherinfo；//其它數據項，類型InfoType依賴于具體應用而定義
?? }RecType；
? typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
? 注意：
??? 若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字符串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。
|