排序程序

/* 待排记录的数据类型 */ #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b))

#define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */ typedef int KeyType; /* 定义关键字类型为整型 */ typedef struct {

KeyType key; /* 关键字项 */

InfoType otherinfo; /* 其它数据项，具体类型在主程中定义 */ }RedType; /* 记录类型 */

typedef struct {

RedType r[MAXSIZE+1]; /* r[0]闲置或用作哨兵单元 */ int length; /* 顺序表长度 */ }SqList; /* 顺序表类型 */

/* bo10-1.c 顺序表插入排序的函数*/ void InsertSort(SqList *L)

{ /* 对顺序表L作直接插入排序。算法10.1 */ int i,j;

for(i=2;i<=(*L).length;++i)

if ((*L).r[i].key<(*L).r[i-1].key)

/* \需将L.r[i]插入有序子表 */

{

(*L).r[0]=(*L).r[i]; /* 复制为哨兵 */ for(j=i-1; ((*L).r[0].key<(*L).r[j].key);--j)

(*L).r[j+1]=(*L).r[j]; /* 记录后移 */ (*L).r[j+1]=(*L).r[0]; /* 插入到正确位置 */ } }

/* algo10-3.c 希尔排序 */ #include

typedef int InfoType; /* 定义其它数据项的类型 */ #include\ #include\

void ShellInsert(SqList *L,int dk)

{ /* 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比， */ /* 作了以下修改： */

/* 1.前后记录位置的增量是dk,而不是1; */

/* 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4 */ int i,j;

for(i=dk+1;i<=(*L).length;++i) if LT((*L).r[i].key,(*L).r[i-dk].key) { /* 需将(*L).r[i]插入有序增量子表 */ (*L).r[0]=(*L).r[i]; /* 暂存在(*L).r[0] */

for(j=i-dk;j>0&<((*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(\ printf(\ }

void print1(SqList L) { int i;

for(i=1;i<=L.length;i++)

printf(\

printf(\ }

void ShellSort(SqList *L,int dlta[],int t)

{ /* 按增量序列dlta[0..t-1]对顺序表L作希尔排序。算法10.5 */ int k;

for(k=0;k

ShellInsert(L,dlta[k]); /* 一趟增量为dlta[k]的插入排序 */ printf(\第%d趟排序结果: \ print(*L); } }

#define N 10 #define T 3 void 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 i,dt[T]={5,3,1}; /* 增量序列数组 */ for(i=0;i

ShellSort(&l,dt,T); printf(\排序后: \ print1(l); }

/* algo10-4.c 起泡排序的程序 */

#define N 8

void bubble_sort(int a[],int n)

{ /* 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序) */ int i,j,t;

Status change;

for(i=n-1,change=TRUE;i>1&&change;--i) {

change=FALSE; for(j=0;ja[j+1]) {

t=a[j];

a[j]=a[j+1]; a[j+1]=t;

change=TRUE; } } }

void print(int r[],int n) {

int i;

for(i=0;i

printf(\ printf(\

}

void main() {

int d[N]={49,38,65,97,76,13,27,49}; printf(\排序前:\\n\ print(d,N);

bubble_sort(d,N);