一、插入排序
1 排序思想
將待排序的記錄Ri，插入到已排好序的記錄表R1, R2 ,…., Ri-1中，得到一個新的、記錄數增加1的有序表。 直到所有的記錄都插入完為止。復雜度為O(n2) 。
設待排序的記錄順序存放在數組R[1…n]中，在排序的某一時刻，將記錄序列分成兩部分：
◆ R[1…i-1]：已排好序的有序部分；
◆ R[i…n]：未排好序的無序部分。
顯然，在剛開始排序時，R[1]是已經排好序的。
例：設有關鍵字序列為：7, 4, -2, 19, 13, 6，直接插入排序的過程如下圖所示：
代碼如下：
//直接插入排序
[cpp]
void straight_insert_sort(int *L,intlength)
{
inti, j,temp ;
for(i=1; i<=length; i++)
{
temp=L[i];
j=i-1; /* 設置哨兵 */
while(temp<L[j])
{ L[j+1]=L[j];
j--;
} /* 查找插入位置 */
L[j+1]=temp; /* 插入到相應位置 */
}
}
void straight_insert_sort(int *L,intlength)
{
inti, j,temp ;
for(i=1; i<=length; i++)
{
temp=L[i];
j=i-1; /* 設置哨兵 */
while(temp<L[j])
{ L[j+1]=L[j];
j--;
} /* 查找插入位置 */
L[j+1]=temp; /* 插入到相應位置 */
}
}
二、 選擇排序
最簡單的排序算法，過程如下：選出數組中最小的元素，將它與數組中第一個元素交換。然後找出次小的元素，將它與數組中第二個元素交換，一直持續下去，直到整個數組排序結束。之所叫選擇排序，是因為它不斷選出剩余元素中的最小元素來實現。
實現代碼如下：
[cpp]
oid selection(Item a[],int l,int r)
{
int i,j;
for(i=l;i<r;i++)
{
intmin=i;//最小元素索引
for(j=i+1;j<=r;j++)
{
if(less(a[j]),a[min])
{
min=j;//更新最小元素的索引值
}
}
exch(a[i],a[min]);//交換
}
}
void selection(Item a[],int l,int r)
{
int i,j;
for(i=l;i<r;i++)
{
intmin=i;//最小元素索引
for(j=i+1;j<=r;j++)
{
if(less(a[j]),a[min])
{
min=j;//更新最小元素的索引值
}
}
exch(a[i],a[min]);//交換
}
}
選擇排序的執行時間由比較操作的數目決定，所使用的次數大概是
：比較操作次數N*N/2,交換操作次數是 N次。而且選擇排序的時間消耗與當前序列的排序狀態無關。
三、 希爾排序
希爾排序時插入排序的擴展，他通過允許非相鄰的元素進行交換來提高執行效率。希爾排序的本質：h-排序，是每第h個元素產生一個排序好的文件。h-排序的文件時h個獨立的已排序好的文件，相互交叉在一起。對h值較大的h排序文件，可以移動相距較遠的元素，比較容易的使h值較小時進行h排序，通過直到1的h值的排序，產生有序文件。
[cpp]
void hell(int *data,int left,int right)
{
intlen=right-left+1;
intd=len;
while(d>1)
{
d=(d+1)/2;
for(int i=left;i<right+1-d;i++)
{
if(data[i+d]<data[i])
{
inttmp=data[i+d];
data[i+d]=data[i];
data[i]=tmp;
}
}
}
}
void hell(int *data,int left,int right)
{
intlen=right-left+1;
intd=len;
while(d>1)
{
d=(d+1)/2;
for(int i=left;i<right+1-d;i++)
{
if(data[i+d]<data[i])
{
inttmp=data[i+d];
data[i+d]=data[i];
data[i]=tmp;
}
}
}
}
希爾排序要選擇一個比較好的步長序列。
四、 冒泡排序
冒泡排序很簡單：遍歷文件，如果緊鄰的兩個元素順序不對，就將兩者交換，重復這個操作，直到整個序列排好序。對於l~r-1的i值，內部循環j通過從右到左遍歷元素，對連續的元素執行比較—交換操作，實現將a[i],…a[r]中最小的元素放大a[i]中。在所有的比較操作中，最小的元素都要移動，冒到最前端。
[cpp]
void maopao(Item a[],int l,int r)
{
inti,j;
for(i=l;i<r;i++)
{
for(j=r;j>i;j--)
{
if(less(a[j],a[j-1]))
{
Itemtemp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
}
void maopao(Item a[],int l,int r)
{
inti,j;
for(i=l;i<r;i++)
{
for(j=r;j>i;j--)
{
if(less(a[j],a[j-1]))
{
Itemtemp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
}
在最壞情況和平均情況下，冒泡排序執行大約N*N/2次比較操作和N*N/2次交換操作。
五、快速排序
快速排序算法是一種分治排序算法，它將數組劃分為兩部分，然後分別對這兩部分進行排序。它將重排序數組，使之滿足一下三個條件：
1，對於某個i，a[i]在最終的位置上
2，a[l]…a[i-1]中的元素都比a[i]小
3，a[i+1] …a[r]中的元素都比a[i]大
通過劃分後完成本輪排序，然後遞歸地處理子文件。
如果數組中有一個或者0個元素，就什麼都不做。否則，調用以下算法實現快速排序：
[cpp]
int partition(Itema[],int l,int r)
{
int i=l-1,j=r;
Item v=a[r];
for (;;)
{
while (less(a[++i],v))
{
;
}
while (less(v,a[--j]))
{
if (j==1)
{
break;
}
}
if (i>=j)
{
break;
}
exch(a[i],a[j]);
}
exch(a[i],a[r]);
return i;
}
int partition(Itema[],int l,int r)
{
int i=l-1,j=r;
Item v=a[r];
for (;;)
{
while (less(a[++i],v))
{
;
}
while (less(v,a[--j]))
{
if (j==1)
{
break;
}
}
if (i>=j)
{
break;
}
exch(a[i],a[j]);
}
exch(a[i],a[r]);
return i;
}
變量v保存了劃分元素a[r]，i和j分別是左掃描指針和右掃描指針。劃分循環使得i增加j減小，while循環保持一個不變的性質---------i左側沒有元素比v大，j右側沒有元素比v小。一旦兩個指針相遇，我們就交換啊a[i]和a[r]，，這樣v左側的元素都小於v，v右側的元素都大於等於v，結束劃分過程。
劃分是一個不確定的過程，當兩個指針相遇，就通過break語句結束。測試j==1用來防止劃分元素是文件總的最小元素。
[cpp]
voidquichsort(Item a[],int l,int r)
{
int i;
if (r<=l)
{
return;
}
i=partition(a,l,r);
quichsort(a,l,i-1);
quichsort(a,i+1,r);
}
voidquichsort(Item a[],int l,int r)
{
int i;
if (r<=l)
{
return;
}
i=partition(a,l,r);
quichsort(a,l,i-1);
quichsort(a,i+1,r);
}
注：快速排序是一個遞歸劃分過程，我們對一個文件進行劃分，劃分原則是將一些元素放在它最終的位置上，對數組進行排序使比劃分元素小的元素都在劃分元素的左邊，比劃分元素大的元素都在劃分元素的右邊，然後分別對左右兩部分進行遞歸處理。然後，從數組的左端進行掃描，直到找到一個大於劃分元素的元素，同時從數據的右端開始掃描，直到找到一個小於劃分元素的元素。使掃描停止的這個兩個元素，顯然在最終的劃分數組中的位置相反，於是交換二者。繼續這一過程，我們就可以保證比劃分元素小的元素都在劃分元素的左邊，比劃分元素大的元素都在劃分元素的右邊。
