第十章内部排序 10.23 void Insert_ Sortl( Sqlist&Ly监视哨设在高下标端的插入排序算法 k=L length for(i=k-1;i-i)∥从后向前逐个插入排序 if(L r[i].key>L r[i+1].key) Lrk+1]key=Lr[key;∥监视哨 for(F=i+1: L rl. key>L ri. key; ++D) Lr[-l]Jkey=Lr]key,/前移 Lr[j-1]key=Lrk+l]key;∥插入 i//nsert Sort 1 10.24 void bilnsert sort( Sqlist&Ly二路插入排序的算法 int d MAXSIZE],辅助存储 first=l final=1 for(F2 K<=L length; i++) if(Lr]key>=x)∥插入前部 for(=final; diPL. r].key j--) dl+=dul; d[+l=.ri final+ else/插入后部 for(=first; d [k<L ri].key:j++) dG-2)%MAXSIZE+1]=L r].key: fist=( first2)% MAXSIZE+1;∥这种形式的表达式是为了兼顾 first=1的情 for(i= first , j=1d[i=%MAXSIZE+1Jj+)将序列复制回去
第十章 内部排序 10.23 void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 { k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)//二路插入排序的算法 { int d[MAXSIZE]; //辅助存储 x=L.r .key;d =x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x) //插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else //插入后部 { for(j=first;d[j]<L.r[i].key;j++) d[j-1]=d[j]; d[(j-2)%MAXSIZE+1]=L.r[i].key; first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾 first=1 的情 况 } }//for for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去
L r0.key=d[; i //BiInsert Sort 10.25 void slinsert_Sort( SLList&L静态链表的插入排序算法 L r[0]. key=0; L r[O Lr[l]next=0;∥建初始循环链表 for(i=2= L length;计+)∥逐个插入 p=0; xL. r[i]. key while(l rL. rp). next]. key<x&&L rIp). next) p=L rp].next q=LrIp).next L rp].next=i L ri]. next=q g//for p=L r[O].next for(i=1< L length;i+)∥重排记录的位置 while(p<i) p=L rIp]. next q=L rp]. next if(pl=i L. rIpk->L rp r[]. next=p: i//for M//SLInsert Sort 10.26 void Bubble_ Sortl(inta[] int n )/对包含n个元素的数组a进行改进的冒泡排序 change=n-1;∥ change指示上一趟冒泡中最后发生交换的元素 while(change) for(c=0, F0; K<change; i++) if(aiAi+ID aj<->a[i+1] C=计+1;∥指示这一趟冒泡中发生交换的元素
L.r[j].key=d[i]; }//BiInsert_Sort 10.25 void SLInsert_Sort(SLList &L)//静态链表的插入排序算法 { L.r[0].key=0;L.r[0].next=1; L.r[1].next=0; //建初始循环链表 for(i=2;i<=L.length;i++) //逐个插入 { p=0;x=L.r[i].key; while(L.r[L.r[p].next].key<x&&L.r[p].next) p=L.r[p].next; q=L.r[p].next; L.r[p].next=i; L.r[i].next=q; }//for p=L.r[0].next; for(i=1;i<L.length;i++) //重排记录的位置 { while(p<i) p=L.r[p].next; q=L.r[p].next; if(p!=i) { L.r[p]<->L.r[i]; L.r[i].next=p; } p=q; }//for }//SLInsert_Sort 10.26 void Bubble_Sort1(int a[ ],int n)//对包含 n 个元素的数组 a 进行改进的冒泡排序 { change=n-1; //change 指示上一趟冒泡中最后发生交换的元素 while(change) { for(c=0,i=0;i<change;i++) if(a[i]>a[i+1]) { a[i]<->a[i+1]; c=i+1; //c 指示这一趟冒泡中发生交换的元素 }
change=c i//while 3//Bubble Sort I 10.27 void Bubble_Sort2(inta[]ntn相邻两趟是反方向起泡的冒泡排序算法 low=0high=n-1;/冒泡的上下界 while(low<high&&change) change=0 for(i=ow,i<hgh;+)∥从上向下起泡 if(aPai+ID ak->a[i+1, change=1 high-;∥/修改上界 for(i=high;p>lowi-)∥从下向上起泡 if(aik<) a<->ai-1; change- low+;∥/修改下界 i//while //Bubble Sort2 void Bubble_Sort3(inta[] ,int n)对上一题的算法进行化简,循环体中只包含一次 冒泡 intb[3/b[0]为冒泡的下界b2]为上界b[无用 d=1b[0}=0b[2]=n-1;/d为冒泡方向的标识1为向上,1为向下 change=1 whileb[okb[ 2 ] &&change) for(i=b[1-d]l-b[tdl计+=d)∥统一的冒泡算法 if(-a[i+d])*d>0)∥注意这个交换条件 aj<->a[i+d]:
change=c; }//while }//Bubble_Sort1 10.27 void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1; while(low<high&&change) { change=0; for(i=low;i<high;i++) //从上向下起泡 if(a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i]<a[i-1]) { a[i]<->a[i-1]; change=1; } low++; //修改下界 }//while }//Bubble_Sort2 10.28 void Bubble_Sort3(int a[ ],int n)//对上一题的算法进行化简,循环体中只包含一次 冒泡 { int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用 d=1;b[0]=0;b[ 2 ]=n-1; //d 为冒泡方向的标识,1 为向上,-1 为向下 change=1; while(b[0]<b[ 2 ]&&change) { change=0; for(i=b[1-d];i!=b[1+d];i+=d) //统一的冒泡算法 if((a[i]-a[i+d])*d>0) //注意这个交换条件 { a[i]<->a[i+d];
change=1 b[1+d]-=d;∥修改边界 d*=1;/换个方向 y//while i//Bubble Sort3 void oe sort(nta[], int n)奇偶交换排序的算法 while(change) change=0 for(i=1;i<n-1计+=2)∥对所有奇数进行一趟比较 if(aiAi+ID aj<->a[i+1] change=1 for(i=0in-1;计+=2)∥对所有偶数进行一趟比较 if(aiAi+ID a[→>a[计+1 change=1 i//while 1/OE Sort 分析本算法的结束条件是连续两趟比较无交换发生 typedef struct i int low. } boundary,∥子序列的上下界类型 void QSort NotRecurve(int SQList&Ly快速排序的非递归算法 low=1; high=L length InitStack(S),/S的元素为 boundary类型 whie(ow<high&&! Stack Empty(S)∥注意排序结束的条件 if(high-low>2)∥如果当前子序列长度大于3且尚未排好序
change=1; } b[1+d]-=d; //修改边界 d*=-1; //换个方向 }//while }//Bubble_Sort3 10.29 void OE_Sort(int a[ ],int n)//奇偶交换排序的算法 { change=1; while(change) { change=0; for(i=1;i<n-1;i+=2) //对所有奇数进行一趟比较 if(a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } for(i=0;i<n-1;i+=2) //对所有偶数进行一趟比较 if(a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } }//while }//OE_Sort 分析:本算法的结束条件是连续两趟比较无交换发生 10.30 typedef struct { int low; int high; } boundary; //子序列的上下界类型 void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法 { low=1;high=L.length; InitStack(S); //S 的元素为 boundary 类型 while(low<high&&!StackEmpty(S)) //注意排序结束的条件 { if(high-low>2) //如果当前子序列长度大于 3 且尚未排好序
pivot= Partition( Llow high),∥进行一趟划分 if(high-pivot>pivot-low) Push(S,{ pivot+ Lhigh};∥把长的子序列边界入栈 high=pvot-l;/短的子序列留待下次排序 else Push(, low, pivot-1)); ow=pivot+1 else if(low<high&& high-low<3y/如果当前子序列长度小于3且尚未排好序 Easy Sort(L, low high),∥直接进行比较排序 low=high,∥当前子序列标志为已排好序 else∥如果当前子序列已排好序但栈中还有未排序的子序列 Pop(S,a),∥从栈中取出一个子序列 low=a low high=a high i//while i//QSort NotRecurve int partition( SQLISt&L, int low, int high)/一趟划分的算法,与书上相同 L rOFL r[low]: pivotkey=L rlow]. key while(low <high) while(low<high&&L r[high]. key>=pivotkey) L row=L rhigh while(low<high&&L r[low).key<=pivotkey) low++ L rhigh=L rlow]: y//while L rlow]=Lr[O] return low 3//Partition
{ pivot=Partition(L,low,high); //进行一趟划分 if(high-pivot>pivot-low) { Push(S,{pivot+1,high}); //把长的子序列边界入栈 high=pivot-1; //短的子序列留待下次排序 } else { Push(S,{low,pivot-1}); low=pivot+1; } }//if else if(low<high&&high-low<3)//如果当前子序列长度小于 3 且尚未排好序 { Easy_Sort(L,low,high); //直接进行比较排序 low=high; //当前子序列标志为已排好序 } else //如果当前子序列已排好序但栈中还有未排序的子序列 { Pop(S,a); //从栈中取出一个子序列 low=a.low; high=a.high; } }//while }//QSort_NotRecurve int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同 { L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low<high) { while(low<high&&L.r[high].key>=pivotkey) high--; L.r[low]=L.r[high]; while(low<high&&L.r[low].key<=pivotkey) low++; L.r[high]=L.r[low]; }//while L.r[low]=L.r[0]; return low; }//Partition