插入排序 -- 直接插入排序、折半排序、希尔排序

?数据定义

typedef int KeyType;
typedef int InfoType;
typedef struct {
?? ?KeyType key;
?? ?InfoType data;
}RecType;

直接插入排序

// 直接插入排序
void InsertSort(RecType R[], int n)
{
?? ?int i, j;
?? ?RecType tmp;
?? ?for (i = 1; i < n; i++)
?? ?{
?? ??? ?if (R[i].key < R[i - 1].key) //前面几个必然有序
?? ??? ?{
?? ??? ??? ?tmp = R[i];
?? ??? ??? ?j = i - 1;
?? ??? ??? ?do {
?? ??? ??? ??? ?R[j + 1] = R[j];
?? ??? ??? ??? ?j--;
?? ??? ??? ?} while (j >= 0 && R[j].key > tmp.key); //一个个挪位置
?? ??? ??? ?R[j + 1] = tmp;
?? ??? ?}
?? ?}
}

折半排序

// 折半排序
void BinInsertSort(RecType R[], int n)
{
?? ?int i, j;
?? ?int low, high, mid;
?? ?RecType tmp;
?? ?for (i = 1; i < n; i++)
?? ?{
?? ??? ?if (R[i].key < R[i - 1].key)
?? ??? ?{
?? ??? ??? ?tmp = R[i];
?? ??? ??? ?low = 0;
?? ??? ??? ?high = i - 1;
?? ??? ??? ?while (low <= high)
?? ??? ??? ?{
?? ??? ??? ??? ?mid = (low + high) / 2;
?? ??? ??? ??? ?if (tmp.key < R[mid].key)
?? ??? ??? ??? ??? ?high = mid - 1;
?? ??? ??? ??? ?else
?? ??? ??? ??? ??? ?low = mid + 1;
?? ??? ??? ?}
?? ??? ??? ?for (j = i - 1; j >= high; j--)
?? ??? ??? ??? ?R[j + 1] = R[j];
?? ??? ??? ?R[high + 1] = tmp;
?? ??? ?}
?? ?}
}

希尔排序?

// 希尔排序
void ShellSort(RecType R[], int n)
{
?? ?int i, j, d;
?? ?RecType tmp;
?? ?d = n / 2;
?? ?while (d > 0)
?? ?{
?? ??? ?for (i = d; i < n; i++) ?// 直接插入排序
?? ??? ?{
?? ??? ??? ?tmp = R[i];
?? ??? ??? ?j = i - d;
?? ??? ??? ?while (j >= 0 && tmp.key < R[i].key)
?? ??? ??? ?{
?? ??? ??? ??? ?R[j + d] = R[j];
?? ??? ??? ??? ?j = j - d;
?? ??? ??? ?}
?? ??? ??? ?R[j + d] = tmp;
?? ??? ?}
?? ??? ?d = d / 2;
?? ?}
}