排序 - 排序基本概念 （二）

　　排序算法分析

　　排序算法的基本操作

　　大多數排序算法都有兩個基本的操作

　　() 比較兩個關鍵字的大小;

　　() 改變指向記錄的指針或移動記錄本身

　　注意

　　第()種基本操作的實現依賴於待排序記錄的存儲方式

　　待排文件的常用存儲方式

　　() 以順序表(或直接用向量)作為存儲結構

　　排序過程對記錄本身進行物理重排(即通過關鍵字之間的比較判定將記錄移到合適的位置)

　　() 以鏈表作為存儲結構

　　排序過程無須移動記錄僅需修改指針通常將這類排序稱為鏈表(或鏈式)排序;

　　() 用順序的方式存儲待排序的記錄但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)

　　排序過程只需對輔助表的表目進行物理重排(即只移動輔助表的表目而不移動記錄本身)適用於難於在鏈表上實現仍需

　　避免排序過程中移動記錄的排序方法

　　排序算法性能評價

　　() 評價排序算法好壞的標准

　　評價排序算法好壞的標准主要有兩條

　　① 執行時間和所需的輔助空間

　　② 算法本身的復雜程度

　　() 排序算法的空間復雜度

　　若排序算法所需的輔助空間並不依賴於問題的規模n即輔助空間是O()則稱之為就地排序(InPlaceSou)

　　非就地排序一般要求的輔助空間為O(n)

　　() 排序算法的時間開銷

　　大多數排序算法的時間開銷主要是關鍵字之間的比較和記錄的移動有的排序算法其執行時間不僅依賴於問題的規模還取決

　　於輸入實例中數據的狀態

　　文件的順序存儲結構表示

　　#define n l //假設的文件長度即待排序的記錄數目

　　typedef int KeyType; //假設的關鍵字類型

　　typedef struct{ //記錄類型

　　KeyType key; //關鍵字項

　　InfoType otherinfo;//其它數據項類型InfoType依賴於具體應用而定義

　　}RecType;

　　typedef RecType SeqList[n+];//SeqList為順序表類型表中第個單元一般用作哨兵

　　注意

　　若關鍵字類型沒有比較算符則可事先定義宏或函數來表示比較運算

　　【例】關鍵字為字符串時可定義宏#define LT(ab)(Stromp((a)(b))<)那麼算法中a

　　用C++，則定義重載的算符"<"更為方便。

From:http://tw.wingwit.com/Article/program/sjjg/201311/23809.html