2、直接插入排序
算法：經過i-1遍處理后，L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止

insertsort(struct rec r[]，int n)
{
int i，j;
unsigned long int compare=0，move=0;
for(i=2;i<=n;i++)
{compare++;
r[0]=r[i];
move++;
j=i-1;
while(r[0].key {r[j+1]=r[j];
j--;
move++;
++compare;}
r[j+1]=r[0];
move++;
}
printf("
InsertSort compare= %ld，move= %ld
"，compare，move);
}

3、簡單選擇排序
算法：首先找到數據清單中的最小的數據，然后將這個數據同第一個數據交換位置；接下來找第二小的數據，再將其同第二個數據交換位置，以此類推。

selectsort(struct rec r[]，int n)
{
unsigned long int compare=0，move=0;
int i，j，k;
struct rec w;
for(i=1;i<=n-1;i++)
{ k=i;
for(j=i+1;j<=n;j++)

{ if(r[j].key>r[k].key) {k=j; compare++; }
w=r[i];
r[i]=r[k];
r[k]=w;
move=move+3;

}
}
printf("
SelectSort compare= %ld，move= %ld
"，compare，move);
}

4、快速排序
算法：首先檢查數據列表中的數據數，如果小于兩個，則直接退出程序。如果有超過兩個以上的數據，就選擇一個分割點將數據分成兩個部分，小于分割點的數據放在一組，其余的放在另一組，然后分別對兩組數據排序。
通常分割點的數據是隨機選取的。這樣無論你的數據是否已被排列過，你所分割成的兩個字列表的大小是差不多的。而只要兩個子列表的大小差不多

q(struct rec r[]，int s，int t)
{
int i=s，j=t;
if(s<t)
{
r[0]=r[s]; ++a; c++;
do{
while(j>i&&r[j].key>=r[0].key)
{j--;
++a; }
if(i<j)
{ r[i]=r[j];
i++;
c++; }
while(i<j&&r[i].key<=r[0].key)
{i++;
++a; }
if(i<j)
{ r[j]=r[i];
j--;
c++; }
} while(i<j);
r[i]=r[0];
c++;
q(r，s，j-1);
q(r，j+1，t);
}
}

5. 堆排序
(1) 基本思想：
堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
(2) . 堆的定義: N個元素的序列K1，K2，K3，...，Kn.稱為堆，當且僅當該序列滿足特性：
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

sift(struct rec r[]，int l，int m)
{
int i，j;
struct rec w;
i=l; j=2*i;
w=r[i];
while(j<=m)
{
if(j<m&&r[j].key<r[j+1].key) { j++;
}
if(w.key<r[j].key)
{
r[i]=r[j];
i=j;
j=2*i;
}
else j=m+1;
}
r[i]=w;
}

heapsort(struct rec r[]，int n)
{
unsigned long int compare=-1，move=-1;
struct rec w;
int i;
int a;
for(i=n/2;i>=1;i--) a=sift(r，i，n);
compare++;
move++;

for(i=n;i>=2;i--)
{
w=r[i];
r[i]=r[1];
r[1]=w;
a=sift(r，1，i-1);
compare+=a;
move+=a;
}
}

小結：
1.學會使用隨機函數randomize( ) 為數組賦初值要在頭文件中添加#include
2．在做此程序之前基本上是在理解了各種排序過程以后完成的
3.對排序算法的總結：
(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。
　當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。
　快速排序是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
　堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的