插入排序与快排

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

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

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

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

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

#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-1n个记录相比即完成一次起泡排序。进行下一次操作知道没有进行过记录交换为止。

快速排序

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

算法:

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;
}