C語言多項排序？
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) 當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。
