排序算法是我們常用算法之一，也是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。排序過程中涉及的存儲器不同，可將排序方法分為兩大類：一類是內排序，指的是待排序記錄存放在計算機隨機存儲器中進行的排序過程，內排序有：插入排序、希爾排序、交換排序、快速排序、選擇排序等；另一類是外排序，指的是待排序記錄的數量很大，以致內存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。
下面說一下交換排序，交換排序主要有：冒泡排序和快速排序，快速排序（Quicksort）其實是對冒泡排序的一種改進。
為了方便描述，使用順序表類型定義如下：
#define MAXSIZE 1000
typedef int KeyType;
typedef struct {
KeyType key;
InfoType otherinfo;
}RecType;
typedef struct {
RecType r[MAXSIZE+1];
int length;
}SqList;
冒泡排序
基本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在後面。整個排序過程最多執行n-1趟，它是一種穩定的算法。
C Code：
void BubbleSort(SqList &q)
{
int j,h,p=q.length-1,temp;
for(h=1;h<=p;)
for(j=0;j<p-1;j++)
if(q.r[j].Key>q.r[j+1].key)
{
temp=q.r[j];
q.r[j]=q.r[j+1];
q.r[j+1]=temp;
p=j
}
}
冒泡排序法存在這不足,當排序的數據比較多時排序的時間會明顯延長。具體做法：任意選取某一記錄（通常取第一個記錄），比較其關鍵字與所有記錄的關鍵字，並將關鍵字比它小的記錄全部放在它的前面，將比它大的記錄均存放在它的後面，這樣，經過一次排序之後，可將所有記錄以該記錄所在的分界點分為兩部分，然後分別對這兩部分進行快速排序，直至排序完 ,這就是改進的方法：快速排序。
快速排序
設要排序的數組是a[0]……a[n-1]，
一趟快速排序的算法是：
1）設置兩個變量low、high，排序開始的時候：low=0，low=n-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即 key=a[0]；
3）從J開始向前搜索，即由後開始向前搜索（high=high-1），找到第一個小於key的值a[high]，並與a[low]交換；
4）從I開始向後搜索，即由前開始向後搜索（low=low+1），找到第一個大於key的a[low]，與a[high]交換；
5）重復第3、4、5步，直到 low=high；
示意圖：
C Code:
void QuickSort(SqList &R ,int s,int t)
{
int low, high,Key;
low=s;
high=t;
Key=R.r[s].key;
R.r[0]=R.r[s];
while(low<high)
{
while(high>low&&R.r[high].key>Key)
high--;
if(low<high)
{
R.r[low]=R.r[high];
low++;
}
while(low<high&&R.r[high].key<=Key)
++low;
if(low<high)
{
R.r[high]=R.r[low];
high--;
}
}
R.r[low]=R.r[0];
QuickSort(R,s,low-1);
QuickSort(R,low+1,t);
}
好了，就先說到這裡了。
作者“flute的專欄”
