排序：就是重新排列表中的元素，是表中的元素滿足按關(guān)鍵字遞增或遞減的過(guò)程。為了查找方便，通常要求計(jì)算機(jī)中的表是按關(guān)鍵字有序的。排序的確切定義如下：
輸入：n個(gè)記錄R1,R2, ...，Rn對(duì)應(yīng)的關(guān)鍵字為k1,k2，...，kn。
輸出：輸入序列的一個(gè)重排R1',R2', ...，Rn'，使得有k1'<=k2'<=...<=kn'（其中“<=”辦以換成其他的比較大小的符號(hào))。
算法的穩(wěn)定性：如果待排序表中有兩個(gè)元素Ri、Rj，其對(duì)應(yīng)的關(guān)鍵字keyi=keyj，且排序前Ri在Rj前面，如果使用某—排序算法排序后，Ri仍然在Rj前面，則稱這個(gè)的，否則稱排序算法是穩(wěn)定的，否則稱排序算法是不穩(wěn)定的。需要注意的是，算法是否具有穩(wěn)定性并不能衡量一個(gè)算法的優(yōu)劣，它主要是對(duì)算法的性質(zhì)進(jìn)行描述。
注意：對(duì)于不穩(wěn)定的排序算法，只需舉出一組關(guān)鍵字的實(shí)例說(shuō)明它的不穩(wěn)定性即可。
在排序的過(guò)程中，根據(jù)數(shù)據(jù)元素是否完全在內(nèi)存中，可將排序算法分為兩類：內(nèi)部排序是指在排序期間元素全部存放在內(nèi)存中的排序；外部排序是指在排序期間元素?zé)o法全部同時(shí)存放在內(nèi)存中，必須在排序的過(guò)程中根據(jù)要求不斷地在內(nèi)、外存之間移動(dòng)的排序。
—般情況下，內(nèi)部排序算法在執(zhí)行過(guò)程中都要進(jìn)行兩種操作：比較和移動(dòng)。通過(guò)比較兩個(gè)關(guān)鍵字，確定對(duì)應(yīng)的元素的前后關(guān)系，然后通過(guò)移動(dòng)元素以達(dá)到有序。當(dāng)然，并不是所有的內(nèi)部排序算法都要基于比較操作，事實(shí)上，基數(shù)排序就不是基于比較的。
內(nèi)部排序算法的性能取決于算法的時(shí)間復(fù)雜度和空間復(fù)雜度，而時(shí)間復(fù)雜度一般是由比較和移動(dòng)的次數(shù)來(lái)決定的。
插入排序是一種簡(jiǎn)單直觀的排序方法，其基本思想在于每次將一個(gè)待排序的記錄，按其關(guān)鍵字從小插入到前面已經(jīng)排好序的子序列中，直到全部記錄插入完成。
由插入排序的思想可以引出三個(gè)重要的排序算法：直接插入排序、折半插入排序、希爾排序。
思想：
插入排序的基本操作是在一個(gè)有序表中進(jìn)行查找和插入。先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂Ｕ麄€(gè)排序過(guò)程為進(jìn)行 n-1 趟插入。
算法描述：
1)查找出L(i)在L[1…i-1]中的插入位置k。
2)將L[k…i-1]中所有元素全部后移一個(gè)位置。
3)將L(i)復(fù)制到L(k)。
例如，已知待排序的 一組記錄的初始排 列如下所示:
（1-1）
假設(shè)在排序過(guò)程中，前 4 個(gè)記錄已按關(guān)鍵宇遞增的次序重新排列，構(gòu)成一個(gè)含4個(gè)記錄的有序序列
（1-2）
現(xiàn)要將式(1-1) 中第 5 個(gè)〈即關(guān)鍵字為 76 的〉記錄插入上述序列，以得到一個(gè)新的含5 個(gè)記錄的有序序列。
則首先要在式(1-2) 的序列中進(jìn)行查找以確定 R(76)所應(yīng)插入的位置，然后進(jìn)行插入.
假設(shè)從 R(97) 起向左進(jìn)行順序查攏，由于 65<76<97，則 R(76)應(yīng)插入在 R(65) 和 R(97) 之間，從而得到下列新的有序序列
{ R(38) ，R(49) ，R(6 日，R(76) ，R(97) } （1-3）
稱從式(1-2) 到式(1-3)的過(guò)程為一趟直接插入排序.
一般情況下 ，第 i趟直接插入排序的操作為:在含有i-1 個(gè)記錄的有序子序列 r[1..i-1]中插入一個(gè)記錄 r[i]后 ，變成含有 4 個(gè)記錄的有序子序列 r[1..i] ；并且，和順序查找類似，為了在查找插入位置的過(guò)程中避免數(shù)組下標(biāo)出界，在 r[0] 處設(shè)置監(jiān)視哨。在自 i-1 起往前搜索的過(guò)程中，可以同時(shí)后移記錄。整個(gè)排序過(guò)程為進(jìn)行 n-1 趟插入，即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂?/p>
注：
將r[0]設(shè)立監(jiān)視哨，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用(避免數(shù)組下標(biāo)出界)。算法的書(shū)寫(xiě)都是以r[0]為監(jiān)視哨(r[0]不存數(shù)據(jù)，實(shí)際應(yīng)用中可用變量代替臨時(shí)存儲(chǔ)，但避免數(shù)組下標(biāo)出界)。
示例：
算法：
void InsertSort(ElemType A[] ,int n){ int i,j; for(i=2;i<=n;i++){ //依次將A[2]-A[n]插入到前面已排序序列 if(A[i].key<A[i-1].key){ //若A[i]的關(guān)鍵碼小于其前驅(qū)，需將 A[i]插入有序表 A[0]=A[i]; //復(fù)制為哨兵 for(j=i-1;A[0].key<A[j].key;--j){//從后往前査找待插入位置 A[j+1]=A[j]; //向后挪位 } A[j+1]=A[0]; //復(fù)制到插入位置 } }}
性能分析：
空間效率：僅使用了常數(shù)個(gè)輔助單元，因而空間復(fù)雜度為O(1）.
時(shí)間效率：在排序過(guò)程中，向有序子表中逐個(gè)地插入元素的操作進(jìn)行了n-l趟，每趟操作都分為比較關(guān)鍵字和移動(dòng)元素,而比較次數(shù)和移動(dòng)次數(shù)取決于待排序的初始狀態(tài)。在最好情況下，表中元素已經(jīng)有序，此時(shí)每插入一個(gè)元素，都只需比較一次不用移動(dòng)元素，因而時(shí)間復(fù)雜度為0(n)。
在最壞情況下,表中元素順序剛好與排序結(jié)果中元素順序相反（逆序）時(shí)，總的比較次數(shù)達(dá)到最大，為，總的移動(dòng)次數(shù)也達(dá)到最大，為。
平均情況下，考慮待排序表中元素是隨機(jī)的，此時(shí)可以取上述最好與最壞情況的平均值作為平均情況下的時(shí)間復(fù)雜度，總的比較次數(shù)與總的移動(dòng)次數(shù)均約為。
由此，直接插入排序算法的時(shí)間復(fù)雜度為雖然折半插入排序算法的時(shí)間復(fù)雜度也有，但對(duì)于數(shù)據(jù)量比較小的排序表，折半插入排序往往能表現(xiàn)出很好的性能。
穩(wěn)定性：每次插入元素時(shí)總是從后向前先比較再移動(dòng)，所以不會(huì)出現(xiàn)相同元素相對(duì)位置發(fā)生變化的情況，即直接插入排序是—個(gè)穩(wěn)定的排序方法.
適用性：直接插入排序算法適用于順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的線性表。當(dāng)為鏈?zhǔn)酱鎯?chǔ)時(shí)，可以從前往后查找指定元素的位置。注意：大部分排序算法都僅適用于順序存儲(chǔ)的線性表。
思想：
插入排序的基本操作是在一個(gè)有序表中進(jìn)行查找和插入，注意到該算法中，總是邊比較邊移動(dòng)元素，下面將比較和移動(dòng)操作分離，先找出元素的待插入位置，再統(tǒng)一地移動(dòng)待插入位置之后的所有元素。折半插入排序針對(duì)“查找”進(jìn)行優(yōu)化，主要減少關(guān)鍵字間的比較次數(shù)。
取有序表的中間節(jié)點(diǎn)，與r[0]比較，大于r[0]查找左半子表，小于r[0]查找右半子表;循環(huán)，直到low不小high。
算法：
void InsertSort(ElemType A[] ,int n){ int i,j,low,high,mid; for(i=2;i<=n;i++){ //依次將A[2]-A[n]插入到前面已排序序列 if(A[i].key<A[i-1].key){ //若A[i]的關(guān)鍵碼小于其前驅(qū)，需將 A[i]插入有序表 A[0]=A[i]; //復(fù)制為哨兵 low=1;high=i-1; while(low<high){ mid=(low+high)/2; //取中間點(diǎn) if(A[mid].key>A[0].key) high=mid-1; //查找左半子表 else low=mid+1; //查找右半子表 } for(j=i-1;A[0].key<A[j].key;--j){//從后往前査找待插入位置 A[j+1]=A[j]; //向后挪位 } A[j+1]=A[0]; //復(fù)制到插入位置 } }}
從上述算法中，不難看出折半插入排序僅僅是減少了比較元素的次數(shù)，約為，該比較次數(shù)與待排序表的初始狀態(tài)無(wú)關(guān)，僅取決于表中的元素個(gè)數(shù)n；而元素的移動(dòng)次數(shù)沒(méi)有改變，它依賴于待排序表的初始狀態(tài)。因此，折半插入排序的時(shí)間復(fù)雜度仍為。折半插入排序是一個(gè)穩(wěn)定的排序方法。
注：for循環(huán)
for循環(huán)形式： for（表達(dá)式1；表達(dá)式2；表達(dá)式3），流程圖：
從前面的講解不難看出，直接插入排序算法適用于基本有序的排序表和數(shù)據(jù)量不大的排序表?；谶@兩點(diǎn)，1959年D.L.Shell提出了希爾排序,又稱為縮小增量排序。
思想：
先將待排序表分割成若干個(gè)形如L[i, i+d, i+2d,…i+kd]的“特殊”子表，分別進(jìn)行直接插入排序，當(dāng)整個(gè)表中元素已呈“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行—次直接插入排序。
算法描述：
先取一個(gè)小于n的步長(zhǎng)d1，把表中全部記錄分成d1個(gè)組，所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中，在各組中進(jìn)行直接插入排序；然后取第二個(gè)步長(zhǎng)d2<d1,重復(fù)上述過(guò)程，直到所取到的dt=1，即所有記錄已放在同—組中，再進(jìn)行直接插入排序，由于此時(shí)已經(jīng)具有較好的局部性，故可以很快得到最終結(jié)果。
增量序列的設(shè)置：
到目前為止，尚未求得一個(gè)最好的增量序列，希爾提出的方法是，。
示例：
算法：
void ShellSort (ElemType A[],int n){//對(duì)順序表作希爾插入排序，本算法和直接插入排序相比，作了以下修改：//1.前后記錄位置的增量是dk,不是1 //2.r[0]只是暫存單元，不是哨兵，當(dāng)j<0時(shí)，插入位置已到 for (dk=len/2; dk>=l; dk=dk/2) //步長(zhǎng)變化 for(i=dk+l;i<=n;++i) if (A[i].key<A[i-dk].key) { //需將A[i]插入有序增量子表 A[0]=A[i]; //暫存在 A[0] for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk) A[j+dk]=A[j]； //記錄后移，查找插入的位置 A[j+dk]=A[0]; //插入 }//if }
性能分析：
空間效率：僅使用了常數(shù)個(gè)輔助單元，空間復(fù)雜度為0(1)。
時(shí)間效率：由于希爾排序的時(shí)間復(fù)雜度依賴于增量序列的函數(shù)，這涉及數(shù)學(xué)上尚未解決的難題，所以其時(shí)間復(fù)雜度分析比較困難。當(dāng)n在某個(gè)特定范圍時(shí)，希爾排序的時(shí)間復(fù)雜度約為0(n13)。在最壞情況下希爾排序的時(shí)間復(fù)雜度為0(n2)。
穩(wěn)定性：當(dāng)相同關(guān)鍵字的記錄被劃分到不同的子表時(shí)，可能會(huì)改變它們之間的相對(duì)次序， 因此，希爾排序是一個(gè)不穩(wěn)定的排序方法。例如，表L={3, 2’, 2},經(jīng)過(guò)一趟排序后，L={2, 2', 3},最終排序序列也是L={2, 2', 3},顯然，2與2'的相對(duì)次序已經(jīng)發(fā)生了變化。
適用性：希爾排序算法僅適用于當(dāng)線性表為順序表的情況。
-------------------------------------------------------------------------------------------------------------------------------------
未完待續(xù)
轉(zhuǎn)載需注明轉(zhuǎn)載字樣，標(biāo)注原作者和原博文地址。
聯(lián)系客服
