插入排序与快排

排序使计算机程序中的一种重要操作，它的功能使将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。本文介绍插入排序与快速排序的一些简单算法。

首先由于待排记录的数量不同，使得排序过程中使用到的存储器也不相同，由此可将排序方法分为两大类：

• 内部排序：待排记录在计算机随机存储器中排序
• 外部排序：由于待排记录数量非常大，以致内存不能容纳全部记录，排序过程中还需要访问外存的排序过程

本文讲述的排序方法属于内部排序

为了算法介绍方便，我们把待排记录的数据类型设置如下：

#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct {
	KeyType	key;
	InfoType otherInfo;
} RedType;
typedef struct {
	RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元
	int	length;
} Sqlist;

设定待排记录的初始排列如下：

49 38 65 97 76 13 27 49

插入排序

直接插入排序

算法：

Status insert_sort(Sqlist &l)
{
	for(int i = 2; i <= l.length; i++) {
		if(l.r[i].key < l.r[i-1].key) {
			l.r[0] = l.r[i];
			l.r[i] = l.r[i-1];
		}
		for(int j = i-2; l.r[0].key < l.r[j].key; j--) {
			l.r[j+1] = l.r[j];
			l.r[j] = l.r[0];
		}
	}
}

整个排序过程进行n-1趟插入。先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。

折半插入排序

在直接插入排序的基础上，从减少比较，移动的次数着手，插入排序中的查找操作可以使用折半查找操作来实现。

算法：

Status binary_insert_sort(Sqlist &l)
{
	int low, high, m;
	for(int i = 2; i <= l.length; i++) {
		l.r[0] = l.r[i];
		low = 1; high = i-1;
		while(low < high) {
			m = (low + high) / 2;
			if(l.r[0].key < l.r[m].key) high = m-1;
			else low = m+1;
		}
		for(int j = i-1; j >= high; j--)
			l.r[j+1] = l.r[j];
		l.r[high+1] = l.r[0];
	}
}

折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字的比较次数，而记录的移送次数不变。

希尔排序

又称缩小增量排序。它的基本思想是：先将整个待排记录序列分割成若干个子序列分别直接进行插入排序，待整个序列基本有序时再对全体记录进行一次插入排序。

算法：

Status shell_insert(Sqlist &l, int dk)
{
	for(int i = dk+1; i <= l.length; i++)
		if(l.r[i].key < l.r[i-dk].key) {
			l.r[0] = l.r[i];
			for(int j = i-dk; j > 0 && l.r[j].key > l.r[j+dk].key; j -= dk) {
				l.r[j+dk] = l.r[j];
				l.r[j] = l.r[0];
			}
		}
	return DONE;
}

参数dk是该趟排序中被分割序列的增量

Status shell_sort(Sqlist &l, int *dlta, int t)
{
	for(int i = 0; i < t; i++)
		if( ! shell_insert(l, dlta[i])) err_return("shell_insert() error", ERROR);
	return DONE;
}

在数组dlta[]中存放着每趟shell_insrt()的增量参数，本例程中使用int dlta[] = {5, 3, 1};。

快速排序

快速排序中介绍一些借助交换进行的排序

起泡排序

起泡排序很简单，先将第1个记录的关键字与第2个记录的关键子比较若逆序则交换位置，然后比较第二个记录与第三个记录的关键字，依次类推直至将n-1与n个记录相比即完成一次起泡排序。进行下一次操作知道没有进行过记录交换为止。

快速排序

快速排序的基本思想是：通过一趟排序将待排记录分割成两部分，其中一部分记录的关键字均比另一部分的记录的关键字小，则分别对这两部分记录继续递归进行快速排序

算法：

void qsort(Sqlist &l, int low, int high)
{
	int privotloc;
	if(low < high) {
		privotloc = partition(l, low, high);
		qsort(l, low, privotloc-1);
		qsort(l, privotloc+1, high);
	}
}

partition()函数将序列分割成两部分，前一部分记录的值均比后一部分小。它的返回值是这两部分的分割点的位置，函数原型如下：

int partition(Sqlist &l, int low, int high)
{
	l.r[0] = l.r[low];
	KeyType privotkey = l.r[low].key;
	while(low < high) {
		while(low < high && l.r[high].key >= privotkey) --high;
		l.r[low] = l.r[high];
		while(low < high && l.r[low].key <= privotkey) ++low;
		l.r[high] = l.r[low];
	}
	l.r[high] = l.r[0];
	return low;
}

在调用快速排序时qsort(l, 1, l.length);，也可以封装成快排函数：

Status quick_sort(Sqlist &l)
{
	qsort(l, 1, l.length);
	return DONE;
}