希尔排序快速排序.doc

实验:第十章 排序软件二班 杨文庄 E01014330/希尔排序和快速排序/ 排序.cpp : Defines the entry point for the console application./#include stdafx.h#includestdio.h#includestring.h#includestdlib.h#define OK 1#define N 10#define MAXSIZE 100#define OVERFLOW -1typedef int KeyType;typedef struct int rMAXSIZE+1;/r0闲置或用作哨兵单元 int length;/顺序表长度SqList;/顺序表类型void swap(SqList &L,int i,int j) int temp=L.ri; L.ri=L.rj; L.rj=temp; void print(SqList L)for(int i=1;i=L.length;i+)printf(%d,L.ri);printf(n);void ShellSort(SqList &L)int i,j,k=0;int increment=L.length;doincrement=increment/3+1;/* 增量序列 */for(i=increment+1;i=L.length;i+)if (L.riri插入有序增量子表 */ L.r0=L.ri; /* 暂存在L-r0 */for(j=i-increment;j0 & L.r01);int Partition(SqList &L,int low,int high) int pivotkey;pivotkey=L.rlow; /* 用子表的第一个记录作枢轴记录 */while(lowhigh) /* 从表的两端交替地向中间扫描 */ while(low=pivotkey)high-; swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */ while(lowhigh&L.rlow=pivotkey)low+; swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */return low; /* 返回枢轴所在位置 */void QSort(SqList &L,int low,int high) int pivot;if(lowrlow.high一分为二，算出枢轴值pivot */QSort(L,low,pivot-1);/* 对低子表递归排序 */QSort(L,pivot+1,high);/* 对高子表递归排序 */void QuickSort(SqList &L) QSort(L,1,L.length);int main()int i;int dN=49,38,65,97,76,13,27,49,55,04;SqList La,Lb;for(i=0;iN;i+) La.ri+1=di; La.length=N;Lb=La;printf(排序前顺序表为: );print(La);printf(希尔排序为: n); Shell