6.2.1.1非递归算法
void Sift1(list R，int p，int q) //堆范围为R[p]~R[q]，调整R[p]为堆 { int j;
MPP，R[0]=R[p]; //R[0]作辅助量 j=2*p; while(j<=q) { if(j=R[j].key) break; //跟结点键值大于孩子结点，已经是堆，调整结束 MPP，R[p]=R[j]; //将R[j]换到双亲位置上 p=j; //修改当前被调整结点 j=2*p; //j指向R[p]的左孩子 } MPP，R[p]=R[0]; }
6.2.1.2递归算法
void Sift2(list R，int p，int q) //堆范围为R[p]~R[q]，调整R[p]为堆 { int j; if(p>=q) return; //只有一个元素 j=2*p; if(j>q) return; if(j=R[j].key) return; //根结点关键字已最大 MPP，R[0]=R[j]; //交换R[j]和R[p]，R[0]作辅助量 MPP，R[j]=R[p];MPP，R[p]=R[0]; Sift2(R，j，q); }
6.2.2堆排序算法
void HeapSort(list R，int n) //堆排序主程序 { int i; for(i=n/2;i>=1;i--) Sift1(R，i，n); //建初始堆 for(i=n;i>=2;i--){ //进行n-1趟堆排序 MPP，R[0]=R[1]; //堆顶和当前堆底交换，R[0]作辅助量 MPP，R[1]=R[i];MPP，R[i]=R[0];Sift1(R，1，i-1); }
7、二路归并排序 7.1原理
将待排序记录R[0]到R[n-1]看成n个长度为1的有序子序列区，从第一个子序列开始，
把相邻的子序列两两归并，便得到[n/2]（取整数）个长度为2或1有序的子序列。然后再把这[n/2]个有序的子序列利用上面的方法两两归并，如此反复，直到最后得到一个长度为n的有序序列。
7.2算法
7.2.1一趟归并算法
void Merge(list R，list R1，int low，int mid，int high) {
//合并R的两个子表：R[low]~R[mid]、R[mid+1]~R[high]，结果在R1中 int i，j，k; i=low; j=mid+1; k=low;
while(i<=mid && j<=high)
if(CPP，R[i].key<=R[j].key) MPP，R1[k++]=R[i++]; //取小者复制 else MPP，R1[k++]=R[j++];
while(i<=mid) MPP，R1[k++]=R[i++]; //复制左子表的剩余记录 while(j<=high) MPP，R1[k++]=R[j++]; //复制右子表的剩余记录 }
void MergePass(list R，list R1，int n，int len) {//对R做一趟归并，结果在R1中 int i，j;
i=1; //i指向第一对子表的起始点 while(i+2*len-1<=n) { //归并长度为len的两个子表 Merge(R，R1，i，i+len-1，i+2*len-1);
i=i+2*len; //i指向下一对子表起始点 }
if(i+len-1 else //子表个数为奇数，剩一段 for(j=i;j<=n;j++) //将最后一个子表复制到R1中 MPP，R1[j]=R[j]; } 7.2.2二路归并算法 void MergeSort(list R，list R1，int n){ //对R二路归并排序，结果在R中（非递归） int len; len=1; while(len 四、头文件与主函数等 #include \#include \#include #define CPP C++ #define MPP M++ #define MP2 M+=2 #define MP3 M+=3 const int d=3; const int r=10; const int maxsize=100000; //数据表容量 typedef int datatype; typedef struct { int f,e; } queue; typedef struct { datatype key; //关键字域 datatype key1[d]; int next; } rectype; //记录类型 typedef rectype list[maxsize+2]; //数据表类型，0号单元不用 __int64 C,M; //比较和移动次数 void check(list R,int n) { //检验排序结果 int i; for(i=2;i<=n;i++) if(R[i].key void disp(list R,int n) { //显示排序后的结果 int i; for(i=1;i<=n;i++) { cout< } cout< //直接插入排序，带监视哨(并不改变关键字次数) void InsertSort1(list R,int n) { int i,j; for(i=2;i<=n;i++) { //依次插入R[2],R[3],?,R[n] if(CPP,R[i].key>=R[i-1].key) continue; //R[i]大于有序区最后一个记录，则本趟不需插入 MPP,R[0]=R[i]; //R[0]是监视哨 j=i-1; do { //查找R[i]的插入位置 MPP,R[j+1]=R[j];j--; //记录后移，继续向前搜索 } while(CPP,R[0].key MPP,R[j+1]=R[0]; //插入R[i] } } //直接插入排序，无监视哨 void InsertSort2(list R,int n) { int i,j;rectype x; //x为辅助量(用R[0]代替时间变长) for(i=2;i<=n;i++) { //进行n-1次插入 if(CPP,R[i].key>=R[i-1].key) continue; MPP,x=R[i]; //待排记录暂存到x j=i-1; do { //顺序比较和移动 MPP,R[j+1]=R[j];j--; } while(j>=1 && (CPP,x.key void ShellInsert(list R,int n,int h) { int i,j,k; for(i=1;i<=h;i++) for(j=i+h;j<=n;j+=h) { if(CPP,R[j].key>=R[j-h].key) continue; MPP,R[0]=R[j]; k=j-h; do{ MPP,R[k+h]=R[k];k=k-h; }while(CPP,k>0 && R[0].key void ShellSort(list R,int n) //希尔排序 { int h=n/2; while(h>=1) //各趟插入排序 { ShellInsert(R,n,h); h=h/2; //缩小增量 } } //上升法冒泡排序 void BubbleSort1(list R,int n) { int i,j,flag;rectype x; //x为辅助量(可用R[0]代替) for(i=1;i<=n-1;i++) { //做n-1趟扫描 flag=0; //置未交换标志 for(j=n;j>=i+1;j--) //从下向上扫描 if(CPP,R[j].key MP3,x=R[j];R[j]=R[j-1];R[j-1]=x;//交换 } if(!flag) break; //本趟未交换过记录，排序结束 } } //下沉法，冒泡排序 void BubbleSort2(list R,int n) { int i,j,flag;rectype x; //x为辅助量(可用R[0]代替) for(i=1;i<=n-1;i++) { //做n-1趟扫描 flag=0; //置未交换标志 for(j=1;j<=n-i;j++) //从上向下扫描 if(CPP,R[j].key>R[j+1].key) {//交换记录 flag=1; MP3,x=R[j];R[j]=R[j+1];R[j+1]=x;//交换 }