插入排序的基本思想：每次將一個待排序的元素按其關鍵字大小插入到前面已經排好的子序表中的適當位置，直到全部元素插入完成為止，本次介紹直接插入排序，折半插入排序和希爾排序，
1 直接插入排序
直接插入排序(Straight Insertion Sort)的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含1個元素，無序表中包含有n-1個元素，排序程序中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序程序，
void InerSort(RecType arr[],int n) //arr[0..n-1]遞增排序
{
int i,j;Rectype tmp;
for(i=1;i<n;i++)
{
tmp=arr[i];
j=i-1;
while((j>=0) && (tmp<arr[j]))
{
arr[j+1]=arr[j]; //將關鍵字大于arr[i]的后移
j--;
}
a[j+1]=tmp;
}
}
演算法平均時間復雜度為O(n2),直接插入排序是一種穩定的排序方法，
2 折半插入排序（二分）
演算法的基本程序：
1）計算 0 ~ i-1 的中間點，用 i 索引處的元素與中間值進行比較，如果 i 索引處的元素大，說明要插入的這個元素應該在中間值和剛加入i索引之間，反之，就是在剛開始的位置 到中間值的位置，這樣很簡單的完成了折半；
2）在相應的半個范圍里面找插入的位置時，不斷的用（1）步驟縮小范圍，不停的折半，范圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個元素要插在什么地方；
3）確定位置之后，將整個序列后移，并將元素插入到相應位置，
1 void BinInerSort(RecType arr[],int n)
2 {
3 int i,j,low,high,mid;
4 Rectype tmp;
5 for(i=1;i<n;i++)
6 {
7 if(arr[i]<arr[i-1]) //反序時
8 {
9 tmp=arr[i];
10 low=0; high=i-1;
11 while(low<=high)
12 { mid=(low+high)/2; //取中間位置
13 if(tmp<arr[mid])
14 high=mid-1;
15 else
16 low=mid+1;
17 }
18
19 for(j=i-1;j>=high+1)
20 arr[j+1]=arr[j];
21
22 arr[high+1]=tmp;
23 }
24 }
25 }
演算法平均時間復雜度為O(n2),折半插入排序是一種穩定的排序方法，
3 希爾排序
希爾排序是希爾（Donald Shell）于1959年提出的一種排序演算法，希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序，同時該演算法是沖破O(n2）的第一批演算法之一，它與插入排序的不同之處在于，它會優先比較距離較遠的元素，希爾排序又叫縮小增量排序，
希爾排序是把記錄按下表的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，演算法便終止，
程序演示
1 void ShelSort(RecType arr[],int n) //希爾排序
2 {
3 int i,j,d;
4 RecType tmp;
5 d=n/2; //增量初始值
6 while(d>0)
7 {
8 for(i=d;i<n;i++)
9 {
10 tmp=arr[i]; //對所有組采用直接插入排序
11 j=i-d;
12 while(j>=0 && tmp<arr[j]) //對相隔d個位置一組采用直接插入排序的方法
13 {
14 arr[j+d]=arr[j];
15 j=j-d;
16 }
17 arr[j+d]=tmp;
18 }
19
20 d=d/2; //減小增量
21 }
22
23 }
希爾排序平均時間復雜度為O(n1.3),速度通常比直接插入排序快，不過是不穩定的排序方法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100180.html
標籤：C++
下一篇：C++生成亂數