【精品数据结构】内排序.pptVIP

11.5 归并排序 归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。 将两个有序表直接归并为一个有序表的算法Merge() ： void Merge(RecType R[],int low,int mid,int high) { RecType *R1; int i=low,j=mid+1,k=0; /*k是R1的下标,i、j分别为第1、2段的下标*/ R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); while (i=mid j=high) if (R[i].key=R[j].key) /*将第1段中的记录放入R1中*/ { R1[k]=R[i]; i++;k++; } else /*将第2段中的记录放入R1中*/ { R1[k]=R[j]; j++;k++; } Merge()实现了一次归并 : while (i=mid) /*将第1段余下部分复制到R1*/ { R1[k]=R[i]; i++;k++; } while (j=high) /*将第2段余下部分复制到R1*/ { R1[k]=R[j]; j++;k++; } for (k=0,i=low;i=high;k++,i++) /*将R1复制回R中*/ R[i]=R1[k]; } void MergePass(RecType R[],int length,int n) { int i; for (i=0;i+2*length-1n;i=i+2*length) /*归并length长的两相邻子表*/ Merge(R,i,i+length-1,i+2*length-1); if (i+length-1n) /*余下两个子表,后者长度小于length*/ Merge(R,i,i+length-1,n-1); /*归并这两个子表*/ } MergePass()实现了一趟归并 二路归并排序算法如下： void MergeSort(RecType R[],int n) /*自底向上的二路归并算法*/ { int length; for (length=1;lengthn;length=2*length) MergePass(R,length,n); } * * 第11章 内 排 序 11.6 基数排序 本章小结 11.1 排序的基本概念 11.2 插入排序 11.3 交换排序 11.4 选择排序 11.5 归并排序 11.7 各种内排序方法的比较和选择 11.1 排序的基本概念 所谓排序,就是要整理表中的记录,使之按关键字递增(或递减)有序排列。其确切定义如下： 输入：n个记录,R0,R1,…,Rn-1,其相应的关键字分别为k0,k1,…,kn-1。 输出：R,R,…,R,使得k≤k≤…≤k(或k≥k≥…≥k)。 当待排序记录的关键字均不相同时,排序的结果是惟一的,否则排序的结果不一定惟一。如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的；反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。 在排序过程中,若整个表都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内排序；反之,若排序过程中要进行数据的内、外存交换,则称之为外排序。 待排序的顺序表类型的类型定义如下： typedef int KeyType; /*定义关键字类型*/ typedef struct /*记录类型*/ { KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为 InfoType*/ } RecType; /*排序的记录类型定义*/ 11.2 插入排序 插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。 两种插