生命是一種過程

排序算法分析

1．排序算法的基本操作
??? 　大多數(shù)排序算法都有兩個(gè)基本的操作：
　　(1) 比較兩個(gè)關(guān)鍵字的大小；
　　(2) 改變指向記錄的指針或移動(dòng)記錄本身。
? 注意：
　??? 第(2)種基本操作的實(shí)現(xiàn)依賴于待排序記錄的存儲(chǔ)方式。

2．待排文件的常用存儲(chǔ)方式
（1） 以順序表(或直接用向量)作為存儲(chǔ)結(jié)構(gòu)
??? 排序過程：對記錄本身進(jìn)行物理重排（即通過關(guān)鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲(chǔ)結(jié)構(gòu)
　　排序過程：無須移動(dòng)記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈?zhǔn)?排序；

（3） 用順序的方式存儲(chǔ)待排序的記錄，但同時(shí)建立一個(gè)輔助表(如包括關(guān)鍵字和指向記錄位置的指針組成的索引表)
　　排序過程：只需對輔助表的表目進(jìn)行物理重排（即只移動(dòng)輔助表的表目，而不移動(dòng)記錄本身）。適用于難于在鏈表上實(shí)現(xiàn)，仍需避免排序過程中移動(dòng)記錄的排序方法。

3．排序算法性能評(píng)價(jià)
（1） 評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)
　　評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：
??? 　① 執(zhí)行時(shí)間和所需的輔助空間
??? 　② 算法本身的復(fù)雜程度

（2） 排序算法的空間復(fù)雜度
　　若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
　　非就地排序一般要求的輔助空間為O(n)。

（3） 排序算法的時(shí)間開銷
　　大多數(shù)排序算法的時(shí)間開銷主要是關(guān)鍵字之間的比較和記錄的移動(dòng)。有的排序算法其執(zhí)行時(shí)間不僅依賴于問題的規(guī)模，還取決于輸入實(shí)例中數(shù)據(jù)的狀態(tài)。

文件的順序存儲(chǔ)結(jié)構(gòu)表示

? #define n l00 //假設(shè)的文件長度，即待排序的記錄數(shù)目
? typedef int KeyType； //假設(shè)的關(guān)鍵字類型
? typedef struct{ //記錄類型
??? KeyType key； //關(guān)鍵字項(xiàng)
??? InfoType otherinfo；//其它數(shù)據(jù)項(xiàng)，類型InfoType依賴于具體應(yīng)用而定義
?? }RecType；
? typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個(gè)單元一般用作哨兵
? 注意：
??? 　若關(guān)鍵字類型沒有比較算符，則可事先定義宏或函數(shù)來表示比較運(yùn)算。
【例】關(guān)鍵字為字符串時(shí)，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。