Chap7排序.ppt

第八章 排序 排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~ 排序分类 按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序 按排序所需工作量 简单的排序方法； 先进的排序方法； 基数排序。 排序基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置 8.1 插入排序 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序 希尔排序(缩小增量法) 排序过程： 先取一个正整数d1n； 把所有相隔d1的记录放一组，组内进行直接插入排序； 然后取d2d1，重复上述分组和排序操作； 直至di=1，即所有记录放进一个组中排序为止。 8.2 交换排序 冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止 算法描述 快速排序 基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序 排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[i]，x=rp.key 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录r[j]，并和rp交换(r[i]=r[j]) 再从i+1所指位置起向后搜索，找到第一个关键字大于x的记录r[i]，和rp交换(r[j]=r[i]) 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止 8.3 选择排序 简单选择排序 排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束 8.4 归并排序 归并——将两个或两个以上的有序表组合成一个新的有序表，叫~ 2-路归并排序 排序思想 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到【n/2】个长度为2或1的有序子序列 再两两合并，……如此重复，直至得到一个长度为n的有序序列为止 归并排序过程 假设R[low]~R[m]和R[m+1]~R[high]是存储在同一数组中，且相邻的两个有序子序列，要将它们合并为一个有序序列R1[low]~R1[high]： 1、设置三个指示器i、j和k，其初值分别为这三个记录区的起始位置； 2、合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[k]中，然后将指向被复制记录的指示器[i或j]、指向复制位置的指示器k加1; 3、重复这一过程，直至全部记录被复制到R1[low]和R1[high]中为止。 8.5 排序算法的特点和选用 选用排序算法需考虑的因素： 1、待排序的记录个数n； 2、记录本身的大小； 3、关键字的分布情况； 4、排序稳定性的要求； 5、辅助空间的大小。 排序算法的选用 1、n较小（小于或等于50）时，可采用插入排序和选择排序；当记录本身信息量较大时，可采用直接选择排序。 2、若n较大，可选择快速排序、归并排序。 3、当待排序纪记录安关键字基本有序时，宜选用直接插入排序和起泡排序。 4、当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。 * * 算法描述 例 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97)