南昌大学，数据结构，实验报告

/*DataType info; 记录的其它字段 */ } RecordNode;

typedef struct {

int n; /* n为文件中的记录个数，n

void shellSort(SortObject * pvector, int d) { int i, j, inc;

RecordNode temp, *data = pvector->record; for (inc = d; inc > 0; inc /= 2) { /* inc 为本趟shell排序增量 */ for (i = inc; i < pvector->n; i++) {

temp = data[i]; /* 保存待插入记录Ri*/

for (j = i-inc; j >= 0 && temp.key < data[j].key; j -= inc) data[j+inc] = data[j]; /* 查找插入位置，记录后移 */ data[j+inc] = temp; } } }

SortObject vector={8,

35,27,76,28,90,56,03,03};

int main(){ int i;

shellSort(&vector,4); for(i=0;i<8;i++)

printf(\ getchar(); return 0; }

/* 插入记录Ri */

// 按递增序进行Shell排序

33

C、 快速排序

void QSort (SqList &L, int low, int high) { //对顺序表L中的子序列

L.r[low..high]作快速排序 if (low

pivotloc=Partition(L,low,high); //将L.r[low..high]一分为二

QSort(L,low,pivotloc-1); //对低子表递归排序，pivotloc是枢轴位置 QSort(L,pivotloc+1,high); //对高子表递归排序 } }//QSort

void QuickSort(SqList &L){ //对顺序表L作快速排序。 QSort(L,1,L.length); }//QuickSort 源程序：

#include #define MAXNUM 100 #define TRUE 1 #define FALSE 0 typedef int KeyType; typedef int DataType;

typedef struct {

KeyType key; /* 排序码字段 */ /*DataType info; 记录的其它字段 */ } RecordNode;

typedef struct {

int n; /* n为文件中的记录个数，n

void quickSort(SortObject * pvector, int l, int r) {

34

int i, j;

RecordNode temp, *data = pvector->record;

if (l >= r) return; /* 只有一个记录或无记录，则无须排序 */ i = l; j = r; temp = data[i];

while (i != j) { /* 寻找Rl的最终位置 */ while( data[j].key >= temp.key && j > i )

j--; /* 从右向左扫描，查找第1个排序码小于temp.key的记录 */ if (i < j) data[i++] = data[j]; while( data[i].key <= temp.key && j > i )

i++; /* 从左向右扫描，查找第1个排序码大于temp.key的记录 */ if (i < j) data[j--] = data[i]; }

data[i] = temp; /* 找到Rl的最终位置 */

quickSort(pvector, l, i-1); /* 递归处理左区间 */ quickSort(pvector, i+1, r); /* 递归处理右区间 */ }

SortObject vector = {8,

67,01,88,34,52,20,77,01};

int main(){ int i;

quickSort(&vector, 0, 7); for(i = 0; i < 8; i++)

printf(\ getchar(); return 0; }

直接插入排序结果：

35

希尔排序结果 快速排序

七、实验小结

通过这次实验，使我对排序有了更深一步的认识与了解。对直接插入爱需使一种最简单的排序方法，以及它的基本操作使将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数曾1的有序表有了一个新的认识。实验中作为直接插入排序的时间复杂度为O（n*n）,关键字间的比较次数和移动记录的次数，约为n*n/4。且希尔排序是不稳定排序，子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列等等。

36