[工学]2012 第14次课 第8章 排序2.ppt

数据结构 【算法8-11】两个有序表的合并 void Merge(datatype R[ ], datatype R1[ ], int s, int m , int t) { /*设两个有序子表R[s]..R[m]和R[m+1]..R[t] */ /*将两个有序子表合并为一个有序表R1[s]..R1[t]*/ i=s; j=m+1; k=s; while (i=mj=t) if(R[i].keyR[j].key) R1[k++]=R[i++]; else R1[k++]=R[j++]; while (i=m) R1[k++]=R[i++]; while (j=t) R1[k++]=R[j++]; } 要注意：该合并算法的要求是两个有序子表是相邻的，即R[s]..R[m]和R[m+1]..R[t]。 56 47 69 48 27 98 56 59 38 28 66 47 56 48 69 27 98 56 59 28 38 66 47 48 56 69 27 56 59 98 28 38 66 27 47 48 56 56 59 69 98 28 38 66 27 28 38 47 48 56 56 59 66 69 98 【算法8-12】一趟归并算法 void MergePass(datatype R[ ], datatype R1[ ], int len, int n) {/*len是本趟归并中有序表的长度，从R[1]..R[n]归并到R1[1]..R1[n]中*/ for(i = 1; i + 2*len -1 = n; i = i + 2*len) Merge(R, R1, i, i+len-1, i+2*len-1); /*对两个长度为len 的有序表合并*/ if(i + len - 1 n) Merge(R, R1, i, i+len-1, n); /*一组半的情况*/ else if(i = n) while(i=n) R1[i++]=R[i++]; /*最后一组没有合并者*/ } 【算法8-13】2-路归并排序 void MergeSort(datatype R[ ], datatype R1[ ], int n) { int len=1; while(lenn) { MergePass(R,R1,len,n); len=2*len; MergePass(R1,R ,len,n); len = 2*len; } } 3．2-路归并排序的递归算法 【算法8-14】2-路归并递归算法 void MSort(datatype R[ ], datatype R1[ ], int s, int t) { /*将R[s]…R[t]归并排序为R1[s]…R1[t]*/ if(s==t) R1[s]=R[s]; else {m=(s+t)/2; /*平分*p表*/ MSort(R, R1, s, m); /*递归地将R[s…m]归并为有序的R1[s…m]*/ MSort(R, R1, m+1, t); /*递归地将R[m+1…t]归并为有序的R1[m+1…t]*/ Merge(R1, R, s, m, t); /*将R1[s…m]和R1[m+1…t]归并到R[s…t]*/ } } void MergeSort(datatype R[ ], datatype R1[ ], int n) {/*对排序表R[1]..R[n]作归并排序*/ MSort(R, R1,1, n); } 8.4.1 简单选择排序 ---特点：每次选择的过程是顺序进行的。 1、基本思想： 第1趟，从第1个到第n个记录中选择关键码最小的记录与第1个记录交换； 第2趟，从第2个到第n个记录中选择关键码最小的记录与第2个记录交换； … 第i趟， 从第i个到第n个记录中选择关键码最小的记录与第i个记录交换; … 直到第n-1趟，从最后两个记录中选择较小的记录放置在第n-1 位置。排序结束。 2、示例： 设排序表：49 14 38 74 96 65 49 8 55 27 第1趟之后：8 14 38 74 96