}}// InserSort
源程序：
#include
KeyType key; /* 排序码字段 */
/*DataType info; 记录的其它字段 */ } RecordNode;
typedef struct {
int n; /* n为文件中的记录个数，n void insertSort(SortObject * pvector) { /* 按递增序进行直接插入排序 */ int i, j; RecordNode temp; RecordNode *data = pvector->record; for( i = 1; i < pvector->n; i++ ) { /* 依次插入记录R1, R2?Rn-1 */ temp = data[i]; for ( j = i-1; temp.key < data[j].key && j >= 0; j-- ) data[j+1] = data[j]; // 由后向前找插入位置 将排序码大于ki的记录后移 if( j != i-1 ) data[j+1] = temp; } } SortObject vector = {10, 21, 04, 65, 77, 31, 13, 27, 49, 90, 77}; int main(){ 31 int i; insertSort(&vector); for(i = 0; i < vector.n; i++) printf(\ getchar(); return 0; } B、希尔排序 void ShellInsert(SqList &L, int dk){ for(i=dk+1;i<=L.length;++i) if（LT（L.r[i].key,L.r[i-dk].key））{ L.r[0]=L.r[i]; //需将L.r[i]插入有序增量字表 //暂存在L.r[0] //对顺序表L作一趟希尔插入排序 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]; } }//ShellInsert void ShellSort (SqList &L, int dlta[], int t){ //按增量序列dlta[0..t-1]对顺序表L作希尔排序。 for (k=0;k ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序 }//ShellSort 源程序： #include KeyType key; /* 排序码字段 */ //记录后移，查找插入位置 //插入 32 /*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*/ // 按递增序进行Shell排序 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 */ 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 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