1、好考研真题网-国内各大高校考研真题第十章 内部排序 10.23 void Insert_Sort1(SqList &L)/监视哨设在高下标端的插入排序算法 k=L.length; for(i=k-1;i;-i) /从后向前逐个插入排序 if(L.ri.keyL.ri+1.key) L.rk+1.key=L.ri.key; /监视哨 for(j=i+1;L.rj.keyL.ri.key;+j) L.rj-1.key=L.rj.key; /前移 L.rj-1.key=L.rk+1.key; /插入 /Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)/
2、二路插入排序的算法 int dMAXSIZE; /辅助存储 x=L.r .key;d =x; first=1;final=1; for(i=2;i=x) /插入前部 for(j=final;djL.ri.key;j-) dj+1=dj; dj+1=L.ri.key; final+; else /插入后部 for(j=first;djL.ri.key;j+) dj-1=dj; d(j-2)%MAXSIZE+1=L.ri.key; first=(first-2)%MAXSIZE+1; /这种形式的表达式是为了兼顾first=1的情况 /for for(i=first,j=1;di;i=i%MAXS
3、IZE+1,j+)/将序列复制回去 L.rj.key=di; /BiInsert_Sort 10.25 void SLInsert_Sort(SLList &L)/静态链表的插入排序算法 L.r0.key=0;L.r0.next=1; L.r1.next=0; /建初始循环链表 for(i=2;i=L.length;i+) /逐个插入 p=0;x=L.ri.key; while(L.rL.rp.next.keyx&L.rp.next) p=L.rp.next; q=L.rp.next; L.rp.next=i; L.ri.next=q; /for p=L.r0.next; for(i=1;iL
4、.length;i+) /重排记录的位置 while(pi) p=L.rp.next; q=L.rp.next; if(p!=i) L.rpL.ri; L.ri.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;iai+1) aiai+1; c=i+1; /c指示这一趟冒泡中发生交换的元素 change=c; /while /Bubble
5、_Sort1 10.27 void Bubble_Sort2(int a ,int n)/相邻两趟是反方向起泡的冒泡排序算法 low=0;high=n-1; /冒泡的上下界 change=1; while(lowhigh&change) change=0; for(i=low;iai+1) aiai+1; change=1; high-; /修改上界 for(i=high;ilow;i-) /从下向上起泡 if(aiai-1) aiai-1; change=1; low+; /修改下界 /while /Bubble_Sort2 10.28 void Bubble_Sort3(int a ,in
6、t n)/对上一题的算法进行化简,循环体中只包含一次 冒泡 int b 3 ; /b0为冒泡的下界,b 2 为上界,b1无用 d=1;b0=0;b 2 =n-1; /d为冒泡方向的标识,1为向上,-1为向下 change=1; while(b00) /注意这个交换条件 aiai+d; change=1; b1+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;iai+1) aiai+1
7、; change=1; for(i=0;iai+1) aiai+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(L,low,
8、high); /进行一趟划分 if(high-pivotpivot-low) Push(S,pivot+1,high); /把长的子序列边界入栈 high=pivot-1; /短的子序列留待下次排序 else Push(S,low,pivot-1); low=pivot+1; /if else if(lowhigh&high-low3)/如果当前子序列长度小于3且尚未排好序 Easy_Sort(L,low,high); /直接进行比较排序 low=high; /当前子序列标志为已排好序 else /如果当前子序列已排好序但栈中还有未排序的子序列 Pop(S,a); /从栈中取出一个子序列 lo
9、w=a.low; high=a.high; /while /QSort_NotRecurve int Partition(SQList &L,int low,int high)/一趟划分的算法,与书上相同 L.r0=L.rlow; pivotkey=L.rlow.key; while(lowhigh) while(low=pivotkey) high-; L.rlow=L.rhigh; while(lowhigh&L.rlow.keyL.rhigh.key) L.rlowL.rhigh; else /子序列含有三个元素 if(L.rlow.keyL.rlow+1.key) L.rlowL.rl
10、ow+1; if(L.rlow+1.keyL.rhigh.key) L.rlow+1L.rhigh; if(L.rlow.keyL.rlow+1.key) L.rlowL.rlow+1; /Easy_Sort 10.31 void Divide(int a ,int n)/把数组a中所有值为负的记录调到非负的记录之前 low=0;high=n-1; while(lowhigh) while(low=0) high-; /以0作为虚拟的枢轴记录 alowahigh; while(lowhigh&alow0) low+; alowahigh; /Divide 10.32 typedef enum
11、RED,WHITE,BLUE color; /三种颜色 void Flag_Arrange(color a ,int n)/把由三种颜色组成的序列重排为按照红,白,蓝 的顺序排列 i=0;j=0;k=n-1; while(j=k) switch(aj) case RED: aiaj; i+; j+; break; case WHITE: j+; break; case BLUE: ajak; k-; /这里没有j+;语句是为了防止交换后aj仍为蓝色的情况 /Flag_Arrange 分析:这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后 的元素全部为蓝色.这样,就
12、可以根据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;
13、p-next-next=t; /交换q和s-next两个结点 /for /LinkedList_Select_Sort 10.34 void Build_Heap(Heap &H,int n)/从低下标到高下标逐个插入建堆的算法 for(i=2;iH.rk.key) H.rjH.rk; j=k; /for /Build_Heap 10.35 void TriHeap_Sort(Heap &H)/利用三叉树形式的堆进行排序的算法 for(i=H.length/3;i0;i-) Heap_Adjust(H,i,H.length); for(i=H.length;i1;i-) H.r1H.ri; H
14、eap_Adjust(H,1,i-1); /TriHeap_Sort void Heap_Adjust(Heap &H,int s,int m)/顺序表H中,H.rs+1到H.rm已经是堆,把 H.rs插入并调整成堆 rc=H.rs; for(j=3*s-1;j=m;j=3*j-1) if(jm&H.rj.keyH.rj+1.key) j+; if(jm&H.rj.keyH.rj+1.key) j+; H.rs=H.rj; s=j; H.rs=rc; /Heap_Adjust 分析:本算法与课本上的堆排序算法相比,只有两处改动:1.建初始堆时,i的上限从H.len gth/3开始(为什么?)
15、2.调整堆的时候,要从结点的三个孩子结点中选择最大的那一个,最 左边的孩子的序号的计算公式为j=3*s-1(为什么?) 10.36 void Merge_Sort(int a ,int n)/归并排序的非递归算法 for(l=1;ln;l*=2) /l为一趟归并段的段长 for(i=0;(2*i-1)*l(n-1)?(n-1):(start2+l-1);/注意end2可能超出边界 Merge(a,start1,end1,start2,end2); /归并 /Merge_Sort void Merge(int a ,int s1,int e1,int s2,int e2)/将有序子序列as1到a
16、e1和 as2到ae2归并为有序序列as1到ae2 int bMAXSIZE; /设立辅助存储数组b for(i=s1,j=s2,k=s1;i=e1&j=e2;k+) if(aiaj) bk=ai+; else bk=aj+; while(i=e1) bk+=ai+; while(j=e2) bk+=aj+; /归并到b中 for(i=s1;i=e2;i+) /复制回去 ai=bi; /Merge 10.37 void LinkedList_Merge_Sort1(LinkedList &L)/链表结构上的归并排序非递归算法 for(l=1;lnext,e2=p;p-next;p=e2) fo
17、r(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为两个子序列的起
18、始位置 while(q!=e1-next&r!=e2-next) if(q-datadata) /选择关键字较小的那个结点接在p的后面 p-next=q;p=q; q=q-next; else 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)/初始归并段为最大有序子序列
19、的归并 排序,采用链表存储结构 LNode *endMAXSIZE; /设立一个数组来存储各有序子序列的尾指针 for(p=L-next-next,i=0;p;p=p-next) /求各有序子序列的尾指针 if(!p-next|p-datap-next-data) endi+=p; while(end0-next) /当不止一个子序列时进行两两归并 j=0;k=0; /j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置 for(p=L-next,e2=p;p-next;p=e2) /两两归并所有子序列 e1=endj;e2=endj+1; /确定两个子序列 if(e1-next)
20、LinkedList_Merge(L,p,e1,e2); /归并 endk+=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) p-next=q;p=q;
21、 q=q-next; else 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.39 void SL_Merge(int a ,int l1,int l2)/把长度分别为l1,l2且l12(l1+l2)的两个 有序子序列归并为有序序列 start1=0;start2=l1; /分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;il1;i+)
22、 /插入第i个元素 for(j=start2;jl1+l2&ajastart1+i;j+); /寻找插入位置 k=j-start2; /k为要向右循环移动的位数 RSh(a,start1,j-1,k);/将astart1到aj-1之间的子序列循环右移k位 start1+=k+1; start2=j; /修改两序列尚未归并部分的起始位置 /SL_Merge void RSh(int a ,int start,int end,int k)/将astart到aend之间的子序列循 环右移k位,算法原理参见5.18 len=end-start+1; for(i=1;i=k;i+) if(len%i=0
23、&k%i=0) p=i; /求len和k的最大公约数p for(i=0;ip;i+) /对p个循环链分别进行右移 j=start+i;l=start+(i+k)%len;temp=aj; while(l!=start+i) aj=temp; temp=al; al=aj; j=l;l=start+(j-start+k)%len; /依次向右移 astart+i=temp; /for /RSh 10.40 书后给出的解题思路在表述上存在问题,无法理解.比如说,把第一个序列划分为两个子 序列,使其中的第一个子序列含有s1个记录,0=s1s,第二个子序列有s个记录.可是题目 中并没有说明,第一个序列
24、的长度2s.请会做的朋友提供解法. 10.41 void Hash_Sort(int a )/对1000个关键字为四位整数的记录进行排序 int b10000; for(i=0;i1000;i+) /直接按关键字散列 for(j=ai;bj;j=(j+1)%10000); bj=ai; for(i=0,j=0;i1000;j+) /将散列收回a中 if(bj) for(x=bj,k=j;bk;k=(k+1)%10000) if(bk=x) ai+=x; bk=0; /if /Hash_Sort 10.42 typedef struct int gt; /大于该记录的个数 int lt; /小于
25、该记录的个数 place; /整个序列中比某个关键字大或小的记录个数 int Get_Mid(int a ,int n)/求一个序列的中值记录的位置 place bMAXSIZE; for(i=0;in;i+) /对每一个元素统计比它大和比它小的元素个数gt和lt for(j=0;jai) bi.gt+; else if(ajai) bi.lt+; mid=0; min_dif=abs(b0.gt-b0.lt); for(i=0;in;i+) /找出gt值与lt值最接近的元素,即为中值记录 if(abs(bi.gt-bi.lt)min_dif) mid=i; return mid; /Get_
26、Mid 10.43 void Count_Sort(int a ,int n)/计数排序算法 int cMAXSIZE; for(i=0;in;i+) /对每一个元素 for(j=0,count=0;jn;j+) /统计关键字比它小的元素个数 if(ajai) count+: ci=count; for(i=0;in;i+) /依次求出关键字最小,第二小,.,最大的记录 min=0; for(j=0;jn;j+) if(cjcmin) min=j; /求出最小记录的下标min aiamin; /与第i个记录交换 cmin=INFINITY; /修改该记录的c值为无穷大以便下一次选取 /Coun
27、t_Sort 10.44 void Enum_Sort(int a ,int n)/对关键字只能取v到w之间任意整数的序列进行排序 int numberw+1,posw+1; for(i=0;in;i+) numberai+; /计数 for(pos0=0,i=1;in;i+) posi=posi-1+numi; /pos数组可以把关键字的值映射为元素在排好的序列中 的位置 for(i=0;in;i+) /构造有序数组c cposai+=ai; for(i=0;in;i+) ai=ci; /Enum_Sort 分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpo
28、 t数组起的是相类似的作用. 10.45 typedef enum 0,1,2,3,4,5,6,7,8,9 digit; /个位数类型 typedef digit3 num; /3位自然数类型,假设低位存储在低下标,高位存储在高下标 void Enum_Radix_Sort(num a ,int n)/利用计数实现基数排序,其中关键字为3位自 然数,共有n个自然数 int number ,pos ; num cMAXSIZE; for(j=0;j3;j+) /依次对个位,十位和百位排序 for(i=0;in;i+) numberaij+; /计数 for(pos0=0,i=1;in;i+) p
29、osi=posi-1+numi; /把关键字的值映射为元素在排好的序列中的位置 for(i=0;in;i+) /构造有序数组c cposaij+=ai; for(i=0;in;i+) ai=ci; /for /Enum_Radix_Sort 分析:计数排序是一种稳定的排序方法.正因为如此,它才能够被用来实现基数排序. 10.46 typedef struct int key; int pos; Shadow; /影子序列的记录类型 void Shadow_Sort(Rectype b ,Rectype &a ,int n)/对元素很大的记录序列b进行 排序,结果放入a中,不移动元素 Shadow dMAXSIZE; for(i=0;i1&change;i-) /对影子序列执行冒泡排序 change=0; for(j=0;jdj+1.key) djdj+1; change=1; /for for(i=0;in;i+) /按照影子序列里记录的原来位置复制原序列 ai=bdi.pos; /Shadow_Sort 更多考研资料，登陆 联系QQ1425536241
