天津科技大学数据结构排序.pptxVIP

? 第十章 排序 概述 插入排序 交换排序 选择排序 归并排序 分配排序 外排序 　排序是计算机中经常遇到的操作。;第十章　排 序 10.1? 概述 排序　计算机内经常进行的一种操作，将一组“无序”的记录序列调整为“有序”的记录序列。 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97;一般，假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 这些关键字相互间可以进行比较，即它们之间存在一个关系　　　　Kp1≤Kp2≤…≤Kpn 按此固有关系将原记录序列重新排列为 { Rp1, Rp2, …，Rpn } 的操作称作排序。 排序算法的稳定性 判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。 　　如 2, 2*,1，排序后若为1, 2*, 2 ，则该排序方法是不稳定的。;内部排序和外部排序 　　若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 　　若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。 内部排序的方法 　　内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。;;10.2 插入排序 假设在排序过程中，记录序列R[1..n]的状态为：;一、直接插入排序 利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。 直接插入排序算法的三个要点： 1、从R[i-1]起向前顺序查找，监视哨设置在R[0]； R[0] = R[i]; // 设置“哨兵” for (j=i-1; R[0].keyR[j].key; --j); // 从后往前找 //循环结束后，可得R[i]的插入位置j+1 2．在查找过程中找到的关键字大于R[0].key的记录需在查找的同时向后移动； for (j=i-1; R[0].keyR[j].key; --j) R[j+1] = R[j]; 3．i = 2，3，…, n, 实现整个序列的排序。;算法描述如下: void InsertionSort ( Elem R[ ], int n) { // 对记录序列R[1..n]作直接插入排序。 　for ( i=2; i=n; ++i ) { 　　R[0] = R[i]; // 复制为监视哨 　　for ( j=i-1; R[0].key R[j].key; --j ) 　　　　R[j+1] = R[j]; // 记录后移 　　R[j+1] = R[0]; // 插入到正确位置 　} } // InsertSort;排序的时间分析： 实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 对于直接插入排序： 最好的情况(关键字在记录序列中顺序有序)： “比较”的次数：1*(n-1)=n-1 “移动”的次数：0 最坏的情况(关键字在记录序列中逆序有序)：;　　直接插入排序是一种稳定的排序方法。原因：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。 二、折半插入排序 　　由于R[1..i-1]是一个按关键字有序的有序序列，则可利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。 　　折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。;void BInsertionSort (Elem R[ ]， int n) { 　// 对记录序列R[1..n]作折半插入排序。 　for ( i=2; i=L.length; ++i ) { 　　R[0] = R[i]; // 将R[i]暂存到R[0] 　　low = 1; high = i-1; 　　while (low=high){//在R[low..high]中折半查找插入的位置 　　　m = (low+high)/2; // 折半 　　　if (R[0].key R[m].key)) high=m-1; 　　　else low = m+1; 　　} 　　for ( j=i-1; j=high+1; --j ) 　　　R[j+1] = R[j]; // 记录后移 　　　R[high+1] = R[0]; // 插入 　　} } // BInsertSort;三、表插入排序 　　为了减少在排序过程中进行的“移动”记录的操作，改变记录的存储结构，利用静态链表进行排序，并在排序完成后，一次性地调整各个记录相互