快速排序
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。大概算法是先找到某一元素的確切位置，再把該元素前後分成兩半，沒找到就移動，找到就賦值！具體做法是先移H，左邊找到比val大的就賦值，右邊找到比它小的就賦值！L和H賦值(L指向第一個元素，H指向最後一個元素，val存放第一個元素的值)。一旦賦值完就不移動！L和H重合了就不需要找了。只要記住一點就行了：左邊找比關鍵字(val)大的就賦值(沒找到就向右移)，右邊找比關鍵字(val)小的就賦值(沒找到就向左移)。 然後利用遞歸的思想（排序依次後，對關鍵字兩邊執行的操作是一樣的）。
舉例說明
49 38 65 97 76 13 27 49] //初始關鍵字
[27 38 13] 49 [76 97 65 49] //第1次劃分完成之後，對應遞歸樹第2層
[13] 27 [38] 49 [49 65] 76 [97] //對上一層各無序區劃分完成後，對應遞歸樹第3層
13 27 38 49 49 [65] 76 97 //對上一層各無序區劃分完成後，對應遞歸樹第4層
13 27 38 49 49 65 76 97 //最後的排序結果
實例代碼
<SPAN style="FONT-SIZE: 14px">#include<stdio.h>
#include<conio.h>
void QuickSort(int *,int,int,int);
int FindPos(int *,int,int);
int num=0;//num用來保存排序進行的趟數
int main()
{
int arr[]={49,38,65,97,76,13,27,49};
int i;
int n=sizeof(arr)/sizeof(int);//用n存放數組長度
printf("***************** 快速排序算法 ******************\n\n");
QuickSort(arr,0,n-1,n);//第二個參數表示第一個元素的下標，第三個參數表示最後一個元素的下標
printf("\n------------- 總共進行了 %d 趟排序！-----------\n",num);
printf("快速排序後的元素為：");
for(i=0;i<n;++i)
printf("%d ",arr[i]);
getch();//暫停程序，等待用戶輸入任意鍵退出程序
return 0;
}
/*進行快速排序，確定第一個元素的確切位置，並將元素分成兩半，左邊一半和右邊一半算法相同，*/
void QuickSort(int *a,int low,int high,int n)
{
int pos=0;
int i;
if(low<high)
{
pos=FindPos(a,low,high);//確定元素的確切位置
printf("第%d趟排序後的元素：",++num);
for(i=0;i<n;++i)
printf("%d ",a[i]);
printf("\n");
QuickSort(a,low,pos-1,n);//前一半進行排序
QuickSort(a,pos+1,high,n);//後一半進行排序
}
}
int FindPos(int *a,int low,int high)
{
int val=a[low];//val作為關鍵字
while(low<high)//每趟排序都從右邊開始
{
while(low<high&&a[high]>=val)
--high;
a[low]=a[high];
while(low<high&&a[low]<=val)
++low;
a[high]=a[low];
}//終止while循環之後low和high的值一定是相等的
a[low]=val;
return low;
}
</SPAN>
注意：
排序算法有3個衡量標准：時間復雜度，空間復雜度，穩定性。穩定性就是能保證排序前兩個相等的數其在序列的前後位置順序和排序後它們兩個的前後位置順序相同。比如甲(60)、乙、丙(60)排完序後甲還是在前面就說明這種排序算法穩定，但從運行結果可以看到第3趟和第四趟結果是一樣的，這說明快速排序是一種不穩定的排序算法。
結束語
數據結構的學習暫時告一段落，有關數據結構還有很多東西要去學，畢竟數據結構是我們如何存儲數據及它們之間的關系(重點) 的一個有力武器，數據結構為我們研究線性和非線性(因為我們的內存是線性一維的，所以通常把非線性結構轉化為線性結構來進行存儲)問題提供了方便。 明天開始學習算法!
