1. 引言
本文主要講解一些常見的排序算法。
2. 插入排序
（1 ） 直接插入排序(straight insertion sort)的作法是：每次從無序表中取出第一個元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比較前兩個數,然後把第二個數按大小插入到有序表中; 第二趟把第三個資料與前兩個數從前向後掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。
（2）折半插入排序（binary insertion sort）是對插入排序算法的一種改進，由于排序算法過程中，就是不斷的依次将元素插入前面已排好序的序列中。由于前半部分為已排好序的數列，這樣我們不用按順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。
折半插入排序算法的具體操作為：在将一個新元素插入已排好序的數組的過程中，尋找插入點時，将待插入區域的首元素設定為a[low],末元素設定為a[high]，則輪比較時将待插入元素與a[m],其中m=(low+high)/2相比較,如果比參考元素小，則選擇a[low]到a[m-1]為新的插入區域(即high=m-1)，否則選擇a[m+1]到a[high]為新的插入區域（即low=m+1），如此直至low<=high不成立，即将此位置之後所有元素後移一位，并将新元素插入a[high+1]。
折半插入排序算法是一種穩定的排序算法，比直接插入算法明顯減少了關鍵字之間比較的次數，是以速度比直接插入排序算法快，但記錄移動的次數沒有變，是以折半插入排序算法的時間複雜度仍然為O(n^2)，與直接插入排序算法相同。
（3） 2-路插入排序是在折半插入排序的基礎上再改進之，其目的是減少排序過程中移動記錄的次數，但為此需要n個記錄的輔助空間。時間複雜度為O(n^2)。了解：所謂的2-路，是指優先插入在序列前面或後面，然後再考慮插入到中間。
#include "ds.h"
#define MAX_SIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
typedef int InfoType; // 定義其它資料項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它資料項，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAX_SIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
// 對順序表L作直接插入排序。算法10.1
void InsertSort(SqList &L)
{
int i, j;
for (i = 2; i <= L.length; ++i)
{
if (LT(L.r[i].key, L.r[i-1].key)) // "<",需将L.r[i]插入有序子表
{
L.r[0] = L.r[i]; // 複制為哨兵
for (j = i - 1; LT(L.r[0].key, L.r[j].key); --j)
L.r[j+1] = L.r[j]; // 記錄後移
L.r[j+1] = L.r[0]; // 插入到正确位置
}
}
}
// 對順序表L作折半插入排序。算法10.2
void BInsertSort(SqList &L)
{
int i, j, m, low, high;
for (i = 2; i <= L.length; ++i)
{
L.r[0] = L.r[i]; // 将L.r[i]暫存到L.r[0]
low = 1;
high = i - 1;
while (low <= high) // 在r[low..high]中折半查找有序插入的位置
{
m = (low + high)/2; // 折半
if LT(L.r[0].key, L.r[m].key)
high = m - 1; // 插入點在低半區
else
low = m + 1; // 插入點在高半區
}
for (j = i - 1; j >= high + 1; --j)
L.r[j+1] = L.r[j]; // 記錄後移
L.r[high+1] = L.r[0]; // 插入
}
}
// 2_路插入排序
void P2_InsertSort(SqList &L)
{
int i, j, first, final;
RedType *d;
d = (RedType*)malloc(L.length*sizeof(RedType)); // 生成L.length個記錄的臨時空間
d[0] = L.r[1]; // 設L的第1個記錄為d中排好序的記錄(在位置[0])
first = final = 0; // first、final分别訓示d中排好序的記錄的第1個和最後1個記錄的位置
for (i = 2; i <= L.length; ++i) // 依次将L的第2個～最後1個記錄插入d中
{
// 待插記錄小于d中最小值，插到d[first]之前(不需移動d數組的元素)
if (L.r[i].key < d[first].key)
{
first = (first-1+L.length)%L.length;
d[first] = L.r[i];
}
else if (L.r[i].key > d[final].key)
{
final = final + 1;
d[final] = L.r[i];
}
else
{
// 待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動d數組的元素)
j = final++; // 移動d的尾部元素以便按序插入記錄
while (L.r[i].key < d[j].key)
{
d[(j+1)%L.length] = d[j];
j = (j-1+L.length)%L.length;
}
d[j+1] = L.r[i];
}
}
for (i = 1; i <= L.length; i++) // 把d賦給L.r
L.r[i] = d[(i+first-1)%L.length]; // 線性關系
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l1,l2,l3;
int i;
for(i=0;i<N;i++) // 給l1.r指派
l1.r[i+1]=d[i];
l1.length=N;
l2=l3=l1; // 複制順序表l2、l3與l1相同
printf("排序前:\n");
print(l1);
InsertSort(l1);
printf("直接插入排序後:\n");
print(l1);
BInsertSort(l2);
printf("折半插入排序後:\n");
print(l2);
P2_InsertSort(l3);
printf("2_路插入排序後:\n");
print(l3);
}
3. 希爾排序
希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。
排序過程：先取一個正整數d1<n，把所有序号相隔d1的數組元素放一組，組内進行直接插入排序；然後取d2<d1，重複上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止
初始：d=5 49 38 65 97 76 13 27 49* 55 04 49 13 |-------------------| 38 27 |-------------------| 65 49* |-------------------| 97 55 |-------------------| 76 04 |-------------------| 一趟結果 13 27 49* 55 04 49 38 65 97 76 d=3 13 27 49* 55 04 49 38 65 97 76 13 55 38 76 |------------|------------|------------| 27 04 65 |------------|------------| 49* 49 97 |------------|------------| 二趟結果 13 04 49* 38 27 49 55 65 97 76 d=1 13 04 49* 38 27 49 55 65 97 76 |----|----|----|----|----|----|----|----|----| 三趟結果 04 13 27 38 49* 49 55 65 76 97
#include "ds.h"
/* 希爾排序的基本思想是：先将整個待排序記錄序列分割成為若幹子序列分别進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次直接插入排序 */
#define MAX_SIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
typedef int InfoType; // 定義其它資料項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它資料項，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAX_SIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
// 對順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前後記錄位置的增量是dk，而不是1;
// 2.r[0]隻是暫存單元，不是哨兵。當j<=0時，插入位置已找到。算法10.4
void ShellInsert(SqList &L, int dk)
{
int i, j;
for (i = dk + 1; i <= L.length; i++)
{
// 需将L.r[i]插入有序增量子表
if LT(L.r[i].key, L.r[i-dk].key)
{
L.r[0] = L.r[i]; // 暫存在L.r[0]
for (j = i-dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
L.r[j+dk] = L.r[j]; // 記錄後移，查找插入位置
L.r[j+dk] = L.r[0]; // 插入
}
}
}
void print(SqList L)
{
int i;
for (i = 1; i <= L.length; i++)
{
printf("%d ", L.r[i].key);
}
printf("\n");
}
void print1(SqList L)
{
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
// 按增量序列dlta[0..t-1]對順序表L作希爾排序。算法10.5
void ShellSort(SqList &L, int dlta[], int t)
{
int k;
for (k = 0; k < t; ++k)
{
ShellInsert(L, dlta[k]);
printf("第%d趟排序結果: ", k+1);
print(L);
}
}
#define N 10
#define T 3
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList l;
int dt[T]={5,3,1}; // 增量序列數組
for(int i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序後: ");
print1(l);
}
![[轉]ISUP信令的IAM消息詳細内容[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)