第十章内部排序 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=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=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]. keyL 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; Ka[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;iL.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;ia[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(lowa[i+1, change=1 high-;∥/修改上界 for(i=high;p>lowi-)∥从下向上起泡 if(aikai-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)∥注意这个交换条件 aja[i+d]:
change=c; }//while }//Bubble_Sort1 10.27 void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1; while(lowa[i+1]) { a[i]a[i+1]; change=1; } high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(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]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;ia[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(ow2)∥如果当前子序列长度大于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;ia[i+1]) { a[i]a[i+1]; change=1; } for(i=0;ia[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(low2) //如果当前子序列长度大于 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=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=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
void Easy Sort( SQLISt& Lint low, int high)对长度小于3的子序列进行比较排序 if(high-low=1)∥序列只含两个元素 if(L r[low).key>L r[high). key)L. rllowK->L r[high] else∥子序列含有三个元素 if(L rlow]. key>L rlow+1]. key)L r[low]L r[low+1 if(L rlow+1].key>L r[high).key)L r[low+1]->L r[high]; if(L r[low).key>L r[low+1].key)L. rllowK->L r[low+1] i //Easy sort 1031 void divide(inta[ 1, int n)/把数组a中所有值为负的记录调到非负的记录之前 low=0; high=n-1; while(low=0)hgh-;/以0作为虚拟的枢轴记录 allow]->ahigh] while(low high i/Divide typedef enum{RED, WHITE BLUE} color,∥三种颜色 void Flag Arrange(color al]ntn把由三种颜色组成的序列重排为按照红,白,蓝 的顺序排列 F0 j F =0; k=n-1; switch(aD case red aiKajI: break case WhIte
void Easy_Sort(SQList &L,int low,int high)//对长度小于 3 的子序列进行比较排序 { if(high-low==1) //子序列只含两个元素 if(L.r[low].key>L.r[high].key) L.r[low]L.r[high]; else //子序列含有三个元素 { if(L.r[low].key>L.r[low+1].key) L.r[low]L.r[low+1]; if(L.r[low+1].key>L.r[high].key) L.r[low+1]L.r[high]; if(L.r[low].key>L.r[low+1].key) L.r[low]L.r[low+1]; } }//Easy_Sort 10.31 void Divide(int a[ ],int n)//把数组 a 中所有值为负的记录调到非负的记录之前 { low=0;high=n-1; while(low=0) high--; //以 0 作为虚拟的枢轴记录 a[low]a[high]; while(lowa[high]; } }//Divide 10.32 typedef enum {RED,WHITE,BLUE} color; //三种颜色 void Flag_Arrange(color a[ ],int n)//把由三种颜色组成的序列重排为按照红,白,蓝 的顺序排列 { i=0;j=0;k=n-1; while(ja[j]; i++; j++; break; case WHITE: j++; break;
case blue alKa[k] k-;∥/这里没有计+;语句是为了防止交换后a仍为蓝色的情况 i//Flag A 分析这个算法中设立了三个指针其中j表示当前元素以前的元素全部为红 色k以后的元素全部为蓝色这样,就可以根据j的颜色,把其交换到序列的前部或 者后部 10.3 void Linked List Select Sort( inked List&L∥单链表上的简单选择排序算法 for(p=L p->next->next p=p->next) q-p- for(r=q,s=qr->next;r=r->next)∥在q后面寻找元素值最小的结点 if(r->next->datanext->data ifs!=q)找到了值比q>data更小的最小结点s>next p->next=s->next; s->next=q >next; q->next=p->next->next p->next-next-t }/交换q和s>next两个结点 i/fo B//Linked List Select Sort void Build Heap(Heap&H, int n)从低下标到高下标逐个插入建堆的算法 for(=2H rk].key) H. rok->H r[k]:
case BLUE: a[j]a[k]; k--; //这里没有 j++;语句是为了防止交换后 a[j]仍为蓝色的情况 } }//Flag_Arrange 分析:这个算法中设立了三个指针.其中,j 表示当前元素;i 以前的元素全部为红 色;k 以后的元素全部为蓝色.这样,就可以根据 j 的颜色,把其交换到序列的前部或 者后部. 10.33 void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 { for(p=L;p->next->next;p=p->next) { q=p->next;x=q->data; for(r=q,s=q;r->next;r=r->next) //在 q 后面寻找元素值最小的结点 if(r->next->datanext->data; s=r; } if(s!=q) //找到了值比 q->data 更小的最小结点 s->next { p->next=s->next;s->next=q; t=q->next;q->next=p->next->next; p->next->next=t; } //交换 q 和 s->next 两个结点 }//for }//LinkedList_Select_Sort 10.34 void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法 { for(i=2;iH.r[k].key) H.r[j]H.r[k]; j=k; }
∥fo 3//Build Heap 10.35 void TriHeap Sort(Heap&H∥/利用三叉树形式的堆进行排序的算法 for(FH length/; i>0; i-) Heap Adjust(H, i, H length); for(FHlength, i>l; i-) H r[IK->H rj; Heap Adjust(H, 1, i-1); i//TriHeap sort void Heap adjust(Heap&ints,ntm∥顺序表H中Hrs+1到Hr{m]已经是堆 把Hrs插入并调整成堆 rc=H r[s] forj=3*s-1j<=m=3*-1) if(<m&&H r[l key <H r[+1]. key)j++ if(j<m&&H rl].key <H r[+l].key)j++; Hrs」F=Hr[] r[s 分析:本算法与课本上的堆排序算法相比,只有两处改动1建初始堆时,i的上限从 H! length3开始(为什么?)2调整堆的时候,要从结点的三个孩子结点中选择最大 的那一个最左边的孩子的序号的计算公式为j=3*s-1(为什么?) 10.36 void Merge Sort(inta[ I, int n∥归并排序的非递归算法 for(l=1<n1*=2)M为一趟归并段的段长 for(i=0、2*i-1)+n;计++)作为本趟的归并段序号 start1=2*l*;∥求出待归并的两段的上下界 end l=start 1+1-1 end2=( start2+-1)(n-1)?(n-1)( start2+-1)/注意end2可能超出边界 Merge(a, start lend 1, start2,end2),/归并
}//for }//Build_Heap 10.35 void TriHeap_Sort(Heap &H)//利用三叉树形式的堆进行排序的算法 { for(i=H.length/3;i>0;i--) Heap_Adjust(H,i,H.length); for(i=H.length;i>1;i--) { H.r[1]H.r[i]; Heap_Adjust(H,1,i-1); } }//TriHeap_Sort void Heap_Adjust(Heap &H,int s,int m)//顺序表 H 中,H.r[s+1]到 H.r[m]已经是堆, 把 H.r[s]插入并调整成堆 { rc=H.r[s]; for(j=3*s-1;j(n-1)?(n-1):(start2+l-1);//注意 end2 可能超出边界 Merge(a,start1,end1,start2,end2); //归并
i//Merge Sort void Merge(inta[ int sI, intel,ints2,inte2川将有序子序列as到alel和as2]到 ae2]归并为有序序列asl到ae2] int bIMAXSIZE设立辅助存储数组b for(Fsl j=s2, k=sl; next, e2-p p->next P=e2) for(i=1, q=p Knext; i++, q=q->next); for(F1; inext; i++, q=q->next) e2=q,∥求出两个待归并子序列的尾指针 ifel!le2) Linked List Merge(L, p,el,e2),∥归并 //Linked List Merge SortI void Linked List Merge (Linked List& L LNode* p, LNode el, LNode’e2)/对链表上 的子序列进行归并第一个子序列是从p>next到el,第二个是从el->next到e2 qFp-> next r=el->next;,/和r为两个子序列的起始位置 while(ql=el->next&&rl=e2->next) fq->data- [->data)∥/选择关键字较小的那个结点接在p的后面 p->next=q; p-q qq->next else
} }//Merge_Sort void Merge(int a[ ],int s1,int e1,int s2,int e2)//将有序子序列 a[s1]到 a[e1]和 a[s2]到 a[e2]归并为有序序列 a[s1]到 a[e2] { int b[MAXSIZE]; //设立辅助存储数组 b for(i=s1,j=s2,k=s1;inext,e2=p;p->next;p=e2) { for(i=1,q=p;inext;i++,q=q->next); e1=q; for(i=1;inext;i++,q=q->next); e2=q; //求出两个待归并子序列的尾指针 if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //归并 } }//LinkedList_Merge_Sort1 void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上 的子序列进行归并,第一个子序列是从 p->next 到 e1,第二个是从 e1->next 到 e2 { q=p->next;r=e1->next; //q 和 r 为两个子序列的起始位置 while(q!=e1->next&&r!=e2->next) { if(q->datadata) //选择关键字较小的那个结点接在 p 的后面 { p->next=q;p=q; q=q->next; } else
rr->next y//while while(q=el->next)∥接上剩余部分 p->next=q p-q q=q->next while(r!=e2->next) p->next-r p-r; rr->next g//Linked List Merge 0.38 void Linked List Merge Sort2( Linkedlist&Ly初始归并段为最大有序子序列的归 并排序采用链表存储结构 LNode* end MAXSIZe]∥设立一个数组来存储各有序子序列的尾指针 for(p=L→next->next,i=0pp=p>next)/求各有序子序列的尾指针 if(p->nextp->data>p->next->data)end [i++]p while(end[o]next)∥当不止一个子序列时进行两两归并 j=0k=0,/:当前子序列尾指针存储位置k:归并后的子序列尾指针存储位置 for(p=L→>next,e2=pp> next p=e2)/两两归并所有子序列 el= send dr; e2=end[+1,∥确定两个子序列 f(el->next) Linked List Merge(L,p,el,e2),∥归并 endk+}=e2;用新序列的尾指针取代原来的尾指针 j+=2;,∥转到后面两个子序列 i//while g//Linked List Merge Sort2 void Linked List Merge(Linked List& L LNode* p, LNode*el, LNode*e2∥对链表上 的子序列进行归并第一个子序列是从p->next到el,第二个是从el->next到e2 q=p->next; r=el->next while(ql=el->next&&rl=e2->next) if(q->data<>data
{ p->next=r;p=r; r=r->next; } }//while while(q!=e1->next) //接上剩余部分 { p->next=q;p=q; q=q->next; } while(r!=e2->next) { p->next=r;p=r; r=r->next; } }//LinkedList_Merge 10.38 void LinkedList_Merge_Sort2(LinkedList &L)//初始归并段为最大有序子序列的归 并排序,采用链表存储结构 { LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针 for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针 if(!p->next||p->data>p->next->data) end[i++]=p; while(end[0]->next) //当不止一个子序列时进行两两归并 { j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置 for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列 { e1=end[j];e2=end[j+1]; //确定两个子序列 if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并 end[k++]=e2; //用新序列的尾指针取代原来的尾指针 j+=2; //转到后面两个子序列 } }//while }//LinkedList_Merge_Sort2 void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上 的子序列进行归并,第一个子序列是从 p->next 到 e1,第二个是从 e1->next 到 e2 { q=p->next;r=e1->next; while(q!=e1->next&&r!=e2->next) { if(q->datadata)