数据结构内部排序.ppt

第十章内部排序 一、排序(Sorting) 排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列 内部排序：在排序期间数据对象全部存放在内存的排序； 外部排序：在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 二、排序基本操作 排序的基本操作包括： 比较：比较两个关键字的大小 移动：将记录从一个位置移动至另一个位置 三、排序时间复杂度 排序的时间复杂度可用算法执行中的记录关键字比较次数与记录移动次数来衡量。 四、排序方法的稳定性 如果在记录序列中有两个记录r[i]和r[j], 它们的关键字 key[i] == key[j] , 且在排序之前, 记录r[i]排在r[j]前面。 如果在排序之后, 记录r[i]仍在记录r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 每步将一个待排序的对象, 按其关键字大小, 插入到前面已经排好序的有序表的适当位置上, 直到对象全部插入为止。 一、直接插入排序 当插入第i(i≥1)个对象时, 前面的r[0], r[1], …, r[i-1]已经排好序。 用r[i]的关键字与r[i-1], r[i-2], …的关键字顺序进行比较(和顺序查找类似)，如果小于，则将r[x]向后移动(插入位置后的记录向后顺移) 找到插入位置即将r[i]插入 一、直接插入排序(举例) 已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08 一、直接插入排序(举例) 一、直接插入排序(举例) 一、直接插入排序(举例) 一、直接插入排序(算法实现) void InsertSort (int r[ ], int n ) { // 假设关键字为整型，放在向量r[]中 int i, j, temp; for ( i = 1; i n; i++ ) { temp = r[i]; for ( j = i; j 0; j-- ) {//从后向前顺序比较，并依次后移 if ( temp r[j-1] ) r[j] = r[j-1]; else break; } r[j] = temp; } } 一、直接插入排序(算法分析) 关键字比较次数和记录移动次数与记录关键字的初始排列有关。 最好情况下, 排序前记录已按关键字从小到大有序, 每趟只需与前面有序记录序列的最后一个记录比较1次, 移动2次记录, 总的关键字比较次数为 n-1, 记录移动次数为 2(n-1)。 一、直接插入排序(算法分析) 最坏情况下, 第i趟时第i个记录必须与前面i个记录都做关键字比较, 并且每做1次比较就要做1次数据移动。则总关键字比较次数KCN和记录移动次数RMN分别为 一、直接插入排序(算法分析) 在平均情况下的关键字比较次数和记录移动次数约为 n2/4。 直接插入排序的时间复杂度为O(n2)。 直接插入排序是一种稳定的排序方法 直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法 二、折半插入排序 折半插入排序在查找记录插入位置时，采用折半查找算法 折半查找比顺序查找快, 所以折半插入排序在查找上性能比直接插入排序好 但需要移动的记录数目与直接插入排序相同(为O(n2)) 折半插入排序的时间复杂度为O(n2)。 折半插入排序是一种稳定的排序方法 三、希尔排序 从直接插入排序可以看出，当待排序列为正序时，时间复杂度为O(n) 若待排序列基本有序时，插入排序效率会提高 希尔排序方法是先将待排序列分成若干子序列分别进行插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序 希尔排序又称为缩小增量排序。 三、希尔排序(算法) 首先取一个整数 gap n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中 在每一个子序列中分别施行直接插入排序。 然后缩小间隔 gap, 例如取 gap = gap/2 重复上述的子序列划分和排序工作，直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。 三、希尔排序(举例) 已知待排序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08 三、希尔排序(举例) 三、希尔排序(举例) 三、希尔排序(算法分析) 开始时 gap 的值较大, 子序列中的记录较少, 排序速度较快 随着排序进展, gap 值逐渐变小, 子序列中记录个数逐渐变多,由于前面大多数记录已基本有序, 所以排序速度仍然很快。 Gap的取法有多种。 shell 提出取 gap = ?n/2?，