注意：排序的稳定性
所用的存储结构
#define MAXSIZE 50
typedef int KeyType;
typedef struct{
KeyType key;
/*...其它数据域...*/
} ElemType;
typedef struct{
ElemType data[MAXSIZE + 1];//从下标1开始存储
int length;//元素个数
} SeqList;
插入排序
直接插入排序 O ( n 2 ) O(n^2) O(n2)
void InsertSort(SeqList &L)
{
for (int i = 2; i <= L.length; i ++)//依次插入第2~n个元素
if (L.data[i].key < L.data[i - 1].key)//该元素比前一个元素小
{
L.data[0] = L.data[i];//设置哨兵, 同时data[i]这个元素此时相当于从原位置抽出，准备进行插入，原位置可以存其它元素
int j;
for (j = i - 1; L.data[0].key < L.data[j].key; j --)
L.data[j + 1] = L.data[j];//不断后移
L.data[j + 1] = L.data[0];//插入到该正确位置
}
}
直接插入排序是稳定的。
二分插入排序 O ( n 2 ) O(n^2) O(n2)
void BiInsertSort(SeqList &L)
{
for (int i = 2; i <= L.length; i ++)//依次插入第2~n个元素
{
L.data[0] = L.data[i];//设置哨兵
int l = 1, r = i - 1;//已有序的序列的两端
while (l <= r)//二分查找应该插入的位置
{
int mid = (l + r) / 2;
if (L.data[0].key < L.data[mid].key) r = mid - 1;
else l = mid + 1;
}//循环结束时，l比r大1，l即是要插入的位置
for (int j = i - 1; j >= l; j --) L.data[j + 1] = L.data[j];//元素后移，将第l位空出来
L.data[l] = L.data[0]; //插入该元素
}
}
希尔排序 O ( n 1.25 ) ∼ O ( 1.6 n 1.25 ) O(n^{1.25})\sim O(1.6n^{1.25}) O(n1.25)∼O(1.6n1.25)
void ShellInsert(SeqList &L, int k)//以k为增量进行插入排序
{
for (int i = k + 1; i <= L.length; i ++)//从该序列中的第二个数开始（第一个数已经有序）
if (L.data[i].key < L.data[i - k].key)//该元素比前一个元素小
{
ElemType temp = L.data[i];//记录该待插入的元素
int j;
for (j = i - k; j > 0 && temp.key < L.data[j].key; j -= k)
L.data[j + k] = L.data[j];//后移
L.data[j + k] = temp;//插入到该位置
}
}
void ShellSort(SeqList &L, int dlta[], int t)
{
for (int i = 0; i < t; i ++)//按增量序列dlta[0 ~ t-1]对该顺序表执行t次插入排序，增量序列是递减的，且最后一个元素为1
ShellInsert(L, dlta[i]);
}
交换排序
冒泡排序 O ( n 2 ) O(n^2) O(n2)
void BubbleSort(SeqList &L)
{
for (int i = 1; i <= L.length - 1; i ++)//总共比较n-1趟
for (int j = 1; j <= L.length - i; j ++)//每趟都从首元素开始比较，第1趟比较n-1次，第2趟比较n-2次，...，第i趟比较n-i次
if (L.data[j].key > L.data[j + 1].key) swap(L.data[j], L.data[j + 1]);
}
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，同时还能部分理顺其它元素。
改进：一旦某一趟不发生交换，说明已经排好序了，可以结束算法。
void BubbleSort(SeqList &L)
{
for (int i = 1; i <= L.length - 1; i ++)//总共比较n-1趟
{
int flag = 0;
for (int j = 1; j <= L.length - i; j ++)
if (L.data[j].key > L.data[j + 1].key)
{
swap(L.data[j], L.data[j + 1]);
flag = 1;
}
if (flag == 0) break;//本趟没有发生交换，已经排好了序
}
}