1、穩定排序和非穩定排序

簡單地說就是所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩定的。反之，就是非穩定的。

比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序後為a1,a2,a4,a3,a5，則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序後它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩定的了。

2、內排序和外排序

在排序過程中，所有需要排序的數都在記憶體，並在記憶體中調整它們的儲存順序，稱為內排序；

在排序過程中，只有部分數被調入記憶體，並藉助記憶體調整數在外存中的存放順序排序方法稱為外排序。

3、演算法的時間複雜度和空間複雜度

所謂演算法的時間複雜度，是指執行演算法所需要的計算工作量。

一個演算法的空間複雜度，一般是指執行這個演算法所需要的記憶體空間。

二、各類排序演算法分析

1、氣泡排序

====================================================

演算法思想簡單描述：

在要排序的一組數中，對當前還未排好序的範圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要求相反時，就將它們互換。

下面是一種改進的冒泡演算法，它記錄了每一遍掃描後最後下沉數的位置k，這樣可以減少外層迴圈掃描的次數。

氣泡排序是穩定的。演算法時間複雜度O(n2)--[n的平方]

=====================================================

＃i nclude <iostream.h>

void BubbleSort(int* pData,int Count)

{

int iTemp;

for(int i=1;i<Count;i++)

{

for(int j=Count-1;j>=i;j--)

{

if(pData[j]<pData[j-1])

{

iTemp = pData[j-1];

pData[j-1] = pData[j];

pData[j] = iTemp;

}

}

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

BubbleSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

倒序(最糟情況)

第一輪：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次)

第二輪：7,10,9,8->7,10,8,9->7,8,10,9(交換2次)

第一輪：7,8,10,9->7,8,9,10(交換1次)

迴圈次數：6次

交換次數：6次

其他：

第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次)

第二輪：7,8,10,9->7,8,10,9->7,8,10,9(交換0次)

第一輪：7,8,10,9->7,8,9,10(交換1次)

迴圈次數：6次

交換次數：3次

上面我們給出了程式段，現在我們分析它：這裡，影響我們演算法效能的主要部分是迴圈和交換，顯然，次數越多，效能就越差。從上面的程式我們可以看出迴圈的次數是固定的，為1+2+...+n-1。寫成公式就是1/2*(n-1)*n。 現在注意，我們給出O方法的定義：

若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n) = O(g(n))。（呵呵，不要說沒 學好數學呀，對於程式設計數學是非常重要的！！！）

現在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我們程式迴圈的複雜度為O(n*n)。再看交換。從程式後面所跟的表可以看到，兩種情況的迴圈相同，交換不同。其實交換本身同資料來源的有序程度有極大的關係，當資料處於倒序的情況時，交換次數同迴圈一樣（每次迴圈判斷都會交換），複雜度為O(n*n)。當資料為正序，將不會有交換。複雜度為O(0)。亂序時處於中間狀態。正是由於這樣的原因，我們通常都是透過迴圈次數來對比演算法。

2、選擇排序

====================================================

演算法思想簡單描述：

在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然後在剩下的數當中再找最小的與第二個位置的數交換，如此迴圈到倒數第二個數和最後一個數比較為止。

選擇排序是不穩定的。演算法複雜度O(n2)--[n的平方]

====================================================

＃i nclude <iostream.h>

void SelectSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=0;i<Count-1;i++)

{

iTemp = pData[i];

iPos = i;

for(int j=i+1;j<Count;j++)

{

if(pData[j]<iTemp)

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData[i];

pData[i] = iTemp;

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

SelectSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

倒序(最糟情況)

第一輪：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1次)

第二輪：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次)

第一輪：7,8,9,10->(iTemp=9)7,8,9,10(交換0次)

迴圈次數：6次

交換次數：2次

其他：

第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1次)

第二輪：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交換1次)

第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次)

迴圈次數：6次

交換次數：3次

遺憾的是演算法需要的迴圈次數依然是1/2*(n-1)*n。所以演算法複雜度為O(n*n)。我們來看他的交換。由於每次外層迴圈只產生一次交換（只有一個最小值）。所以f(n)<=n 所以我們有f(n)=O(n)。所以，在資料較亂的時候，可以減少一定的交換次數。

3、直接插入排序

====================================================

演算法思想簡單描述：

在要排序的一組數中，假設前面(n-1) [n>=2] 個數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反覆迴圈，直到全部排好順序。

直接插入排序是穩定的。演算法時間複雜度O(n2)--[n的平方]

=====================================================

#include <iostream.h>

void SelectSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=0;i<Count-1;i++)

{

iTemp = pData[i];

iPos = i;

for(int j=i+1;j<Count;j++)

{

if(pData[j]<iTemp)

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData[i];

pData[i] = iTemp;

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

SelectSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

倒序(最糟情況)

第一輪：10,9,8,7->9,10,8,7(交換1次)(迴圈1次)

第二輪：9,10,8,7->8,9,10,7(交換1次)(迴圈2次)

第一輪：8,9,10,7->7,8,9,10(交換1次)(迴圈3次)

迴圈次數：6次

交換次數：3次

其他：

第一輪：8,10,7,9->8,10,7,9(交換0次)(迴圈1次)

第二輪：8,10,7,9->7,8,10,9(交換1次)(迴圈2次)

第一輪：7,8,10,9->7,8,9,10(交換1次)(迴圈1次)

迴圈次數：4次

交換次數：2次

上面結尾的行為分析事實上造成了一種假象，讓我們認為這種演算法是簡單演算法中最好的，其實不是，因為其迴圈次數雖然並不固定，我們仍可以使用O方法。從上面的結果可以看出，迴圈的次數f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其複雜度仍為O(n*n)（這裡說明一下，其實如果不是為了展示這些簡單排序的不同，交換次數仍然可以這樣推導）。現在看交換，從外觀上看，交換次數是O(n)（推導類似選擇法），但我們每次要進行與內層迴圈相同次數的‘=’操作。正常的一次交換我們需要三次‘=’ 而這裡顯然多了一些，所以我們浪費了時間。

個人認為在簡單排序演算法中，選擇法是最好的。

4、希爾排序

====================================================

演算法思想簡單描述：

在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點，並且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除

多個元素交換。D.L.shell於1959年在以他名字命名的排序演算法中實現了這一思想。演算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成

一組，排序完成。

下面的函式是一個希爾排序演算法的一個實現，初次取序列的一半為增量，以後每次減半，直到增量為1。

希爾排序是不穩定的。

=====================================================

這個排序非常複雜，看了程式就知道了。 首先需要一個遞減的步長，這裡我們使用的是9、5、3、1（最後的步長必須是1）。工作原理是首先對相隔9-1個元素的所有內容排序，然後再使用同樣的方法對相隔5-1個元素的排序，以次類推。

＃i nclude <iostream.h>

void ShellSort(int* pData,int Count)

{

int step[4];

step[0] = 9;

step[1] = 5;

step[2] = 3;

step[3] = 1;

int i,Temp;

int k,s,w;

for(int i=0;i<4;i++)

{

k = step[i];

s = -k;

for(int j=k;j<Count;j++)

{

iTemp = pData[j];

w = j-k;//求上step個元素的下標

if(s ==0)

{

s = -k;

s++;

pData[s] = iTemp;

}

while((iTemp<pData[w]) && (w>=0) && (w<=Count))

{

pData[w+k] = pData[w];

w = w-k;

}

pData[w+k] = iTemp;

}

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};

ShellSort(data,12);

for (int i=0;i<12;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

呵呵，程式看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕鬆多了，這裡是避免使用0 步長造成程式異常而寫的程式碼。這個程式碼我認為很值得一看。這個演算法的得名是因為其發明者的名字D.L.SHELL。依照參考資料上的說法：“由於複雜的數學原因避免使用2的冪次步長，它能降低演算法效率。”另外演算法的複雜度為n的1.2次冪。同樣因為非常複雜並 “我也不知道過程"，我們只有結果了。

5、快速排序

====================================================

演算法思想簡單描述：

快速排序是對氣泡排序的一種本質改進。它的基本思想是透過一趟掃描後，使得排序序列的長度能大幅度地減少。在氣泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。快速排序透過一趟掃描，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有一個元素為止。它是由C.A.R.Hoare於1962年提出的。

顯然快速排序可以用遞迴實現，當然也可以用棧化解遞迴實現。下面的函式是用遞迴實現的，有興趣的朋友可以改成非遞迴的。

快速排序是不穩定的。最理想情況演算法時間複雜度O(nlog2n)，最壞O(n2)

=====================================================

＃i nclude <iostream.h>

void run(int* pData,int left,int right)

{

int i,j;

int middle,iTemp;

i = left;

j = right;

middle = pData[(left+right)/2]; //求中間值

do{

while((pData[i]<middle) && (i<right))//從左掃描大於中值的數

i++;

while((pData[j]>middle) && (j>left))//從右掃描大於中值的數

j--;

if(i<=j)//找到了一對值

{

//交換

iTemp = pData[i];

pData[i] = pData[j];

pData[j] = iTemp;

i++;

j--;

}

}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）

//當左邊部分有值(left<j)，遞迴左半邊

if(left<j)

run(pData,left,j);

//當右邊部分有值(right>i)，遞迴右半邊

if(right>i)

run(pData,i,right);

}

void QuickSort(int* pData,int Count)

{

run(pData,0,Count-1);

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

QuickSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

這裡我沒有給出行為的分析，因為這個很簡單，我們直接來分析演算法：首先我們考慮最理想的情況

1.陣列的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。

2.每次我們選擇的值剛好是中間值，這樣，陣列才可以被等分。

第一層遞迴，迴圈n次，第二層迴圈2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 所以演算法複雜度為O(log2(n)*n) 其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那麼他將變成交換法（由於使用了遞迴，情況更糟）。但是你認為這種情況發生的機率有多大？？呵呵，你完全不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。如果你擔心這個問題，你可以使用堆排序，這是一種穩定的O(log2(n)*n)演算法，但是通常情況下速度要慢於快速排序（因為要重組堆）。

6、堆排序

====================================================

演算法思想簡單描述：

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。

堆的定義如下：具有n個元素的序列（h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時稱之為堆。在這裡只討論滿足前者條件的堆。

由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項。完全二叉樹可以很直觀地表示堆的結構。堆頂為根，其它為左子樹、右子樹。

初始時把要排序的數的序列看作是一棵順序儲存的二叉樹，調整它們的儲存順序，使之成為一個堆，這時堆的根節點的數最大。然後將根節點與堆的最後一個節點交換。然後對前面(n-1)個數重新調整使之成為堆。依此類推，直到只有兩個節點的堆，並對它們作交換，最後得到有n個節點的有序序列。

從演算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最後一個元素交換位置。所以堆排序有兩個函式組成。一是建堆的滲透函式，二是反覆呼叫滲透函式實現排序的函式。

堆排序是不穩定的。演算法時間複雜度O(nlog2n)。

====================================================

void sift(int *x, int n, int s)

{

int t, k, j;

t = *(x+s);

k = s;

j = 2*k + 1;

while (j

{

if (j

< *(x+j+1)) *判斷是否滿足堆的條件：滿足就繼續下一輪比較，否則調整。* && *(x+j) /> {

j++;

}

if (t<*(x+j))

{

*(x+k) = *(x+j);

k = j;

j = 2*k + 1;

}

else

{

break;

}

}

*(x+k) = t;

}

void heap_sort(int *x, int n)

{

int i, k, t;

int *p;

for (i=n/2-1; i>=0; i--)

{

sift(x,n,i);

}

for (k=n-1; k>=1; k--)

{

t = *(x+0);

*(x+0) = *(x+k);

*(x+k) = t;

sift(x,k,0);

}

}

void main()

{

#define MAX 4

int *p, i, a[MAX];

p = a;

printf("Input %d number for sorting :\n",MAX);

for (i=0; i

{

scanf("%d",p++);

}

printf("\n");

p = a;

select_sort(p,MAX);

for (p=a, i=0; i

{

printf("%d ",*p++);

}

printf("\n");

system("pause");

}

其他的交換法，雙向冒泡法等等就不具體介紹了。

三、幾種排序演算法的比較和選擇

1. 選取排序方法需要考慮的因素：

(1) 待排序的元素數目n；

(2) 元素本身資訊量的大小；

(3) 關鍵字的結構及其分佈情況；

(4) 語言工具的條件，輔助空間的大小等。

四、小結：

(1) 若n較小(n <= 50)，則可以採用直接插入排序或直接選擇排序。由於直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身資訊量較大時，用直接選擇排序較好。

(2) 若檔案的初始狀態已按關鍵字基本有序，則選用直接插入或氣泡排序為宜。

(3) 若n較大，則應採用時間複雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸併排序。快速排序是目前基於比較的內部排序法中被認為是最好的方法。

(4) 在基於比較排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當檔案的n個關鍵字隨機分佈時，任何藉助於"比較"的排序演算法，至少需要O(nlog2n)的時間。

(5) 當記錄本身資訊量較大時，為避免耗費大量時間移動記錄，可以用連結串列作為儲存結構。