|
排序，是將一組對象按照規(guī)定的次序重新排列的過程，排序往往是為檢索服務(wù)的。排序可分為兩大類：內(nèi)部排序和外部排序，我們這里只討論內(nèi)部排序。內(nèi)部排序的方法主要有以下四種：插入排序、交換排序、選擇排序和歸并排序。
一、插入排序
插入排序又分為直接插入排序、折半插入排序、表插入排序和希爾排序。不過我們最常用的就是現(xiàn)在即將介紹的直接插入排序。
直接插入排序：是一種比較簡單的排序方法，它的基本思想是依次將每個記錄插入到一個已排好序的有序表中，從而得到一個新的、記錄數(shù)增加1的有序表。
直接插入排序的算法描述如下：
[csharp]
voidStraightInsertSort(List R, int n)
//對順序表R進行直接插入排序
{
int i, j;
for (i = 2; i <= n; i++) //n為表長，從第二個記錄起進行插入
{
R[0] =R[i]; //第i個記錄復(fù)制為崗哨
j = j - 1;
while(R[0].key<R[j].key) //與崗哨比較，直至鍵值不大于崗哨鍵值
{
R[j + 1] =R[j]; //將第j個記錄賦值給第j+1個記錄
j--;
}
R[j + 1] =R[0]; //將第i個記錄插入到排序中
}
}
應(yīng)用直接插入排序方法：
 這個算法簡單，易于理解，容易實現(xiàn)，時間復(fù)雜度為O（n2），若帶排序記錄的數(shù)量很大時，一般不建議選用直接插入排序。從空間上看，它只需要一個記錄的輔助空間，即空間復(fù)雜度為O（1）。直接插入排序方法是穩(wěn)定的。
二、交換排序
交換排序的基本思想：比較兩個記錄鍵值的大小，如果這兩個記錄鍵值的大小出現(xiàn)逆序，則交換這兩個記錄，這樣將鍵值較小的記錄向序列前部移動，鍵值較大的記錄向序列后部移動。
交換排序又可分為冒泡排序和快速排序，由于本人對快速排序還不甚理解，先主要講述冒泡排序。
冒泡排序法：其過程是首先將第一個記錄的鍵值和第二個記錄的鍵值進行比較，若為逆序（即R[1].key>R[2].key），則將這兩個記錄交換，然后繼續(xù)比較第二個和第三個記錄。依次類推，直到完成第n-1個記錄和第n個記錄的鍵值比較交換位置。上述過程為第一趟起泡，其結(jié)果使鍵值最大的記錄移到了第n個位置上。然后再進行第二趟起泡排序，即對前n-1個記錄進行同樣的操作，其結(jié)果是次大鍵值的記錄安置在第n-1個位置上。重復(fù)以上過程，當(dāng)在一趟起泡過程中沒有進行記錄交換操作時，整個排序過程終止。
看著過程貌似很復(fù)雜，其實冒泡排序是非常簡單的，下面以一個例子來解釋：
初始鍵值序列 45 38 66 90 88 10 25 45
第一趟排序后 38 45 66 88 10 25 45 90
第二趟排序后 38 45 66 10 25 45 88 90
第三趟排序后 38 45 10 25 45 66 88 90
第四趟排序后 38 10 25 45 45 66 88 90
第五趟排序后 10 25 38 45 45 66 88 90
第六趟排序后 10 25 38 45 45 66 88 90
第七趟排序后 10 25 38 45 45 66 88 90（完成）
從上例中可以看出，鍵值較小的記錄好比氣泡一樣向上漂浮，鍵值較大的記錄則向下沉，因為每趟都有一個最大鍵值的記錄沉到水底，所以整個排序過程至多需要進行n-1趟起泡。
冒泡排序的算法描述如下：
[csharp]
Void BubbleSort(List R,int n)
{
int i,j,temp,endsort;
for (i=1;i<=n-1;i++)
{
endsort=0;
for(j=1;j<=n-i-1;j++)
{
if (R[j].key>R[j+1].key) //若逆序則交換記錄
{
temp=R[j];
R[j]=R[j+1];
R[j+1]=temp;
endsort=1;
}
}
if (endsort==0) break;
}
}
在算法實現(xiàn)時，定義一個整型變量endsort，在每一次排序之前，先將他設(shè)置為0，若在一趟起泡中交換了記錄，則將他置位1。當(dāng)一次循環(huán)結(jié)束時，我們再檢查endsort，ruoendsort的值為0便終止算法。
該算法的時間復(fù)雜度為O（n2），是一種穩(wěn)定的排序方法。
|
|
|
