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

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、簡(jiǎn)單選擇排序
算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個(gè)數(shù)據(jù)同第一個(gè)數(shù)據(jù)交換位置；接下來(lái)找第二小的數(shù)據(jù)，再將其同第二個(gè)數(shù)據(jù)交換位置，以此類(lèi)推。

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、快速排序
算法：首先檢查數(shù)據(jù)列表中的數(shù)據(jù)數(shù)，如果小于兩個(gè)，則直接退出程序。如果有超過(guò)兩個(gè)以上的數(shù)據(jù)，就選擇一個(gè)分割點(diǎn)將數(shù)據(jù)分成兩個(gè)部分，小于分割點(diǎn)的數(shù)據(jù)放在一組，其余的放在另一組，然后分別對(duì)兩組數(shù)據(jù)排序。
通常分割點(diǎn)的數(shù)據(jù)是隨機(jī)選取的。這樣無(wú)論你的數(shù)據(jù)是否已被排列過(guò)，你所分割成的兩個(gè)字列表的大小是差不多的。而只要兩個(gè)子列表的大小差不多

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) 基本思想：
堆排序是一樹(shù)形選擇排序，在排序過(guò)程中，將R[1..N]看成是一顆完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。
(2) . 堆的定義: N個(gè)元素的序列K1，K2，K3，...，Kn.稱(chēng)為堆，當(dāng)且僅當(dāng)該序列滿(mǎn)足特性：
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;
}
}

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