数据结构(严蔚敏) 第10章 内部排序(精品·公开课件).ppt

第10章 排序 10.1 概 述 排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。 从第9章的讨论中容易看出，为了查找方便，通常希望计算机中的表是按关键字有序的。又如建造树表(无论是二叉排序树或B-树)的过程本身就是一个排序的过程。因此，学习和研究各种排序方法是计算机工作者的重要课题之一。 为了便于讨论，在此首先要对排序下一个确切的定义 ： 假设含n个记录的序列为 {R1，R2，…，Rn} (10-1) 其相应的关键字序列为 {K1，K2，…，Kn} (10-2) 需确定1，2，…，n的一种排列p1，p2，…，pn，使其 相应的关键字满足如下的非递减(或非递增)关系 Kp1≤Kp2≤…≤Kpn 即使式（10-1）的序列成为一个按关键字有序的序列 {Rp1，Rp2，…，Rpn} 这样一种操作称为排序。 上述排序定义中的关键字Ki可以是记录Ri ( i=1，2，…，n)的主关键字，也可以是记录Ri的次关键字，甚至是若干数据项的组合。若Ki是主关键字，则任何一个记录的无序序列经排序后得到的结果是唯一的；若Ki是次关键字，则排序的结果不唯一，因为待排序的记录序列中可能存在两个或两个以上关键字相等的记录。假设Ki=Kj(1≤i≤ n，1≤j≤n，i!=j)，且在排序前的序列中Ri领先于Rj(即ij)。若在排序后的序列中 Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。 由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类： 一类是内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。 本章集中讨论内部排序 。 内部排序的方法很多，每一种方法都有各自的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择排序、归并排序和计数排序等五类；如果按内部排序过程中所需的工作量来区分，则可分为三类：(1)简单的排序方法，其时间复杂度为O(n2)；(2)先进的排序方法，其时间复杂度为O(nlogn)；(3)基数排序，其时间复杂度为O(d·n)。 10.2 插入排序 一、 直接插入排序 直接插人排序(Straight Insertion Sort)是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。 例如，已知待排序的一组记录的初始排列如下所示： R(49), R(38), R(65), R(97), R(76), R(13), R(27), R(49’), … (10-4) 假设在排序过程中，前4个记录已按关键字递增的次序重新排列，构成一个含4个记录的有序序列 {R(38)，R(49)，R(65)，R(97)} (10-5) 现要将式(10-4)中第5个(即关键字为76的)记录插入上述序列，以得到一个新的含5个记录的有序序列，则首先要在式(10-5)的序列中进行查找以确定R(76)所应插入的位置，然后进行插入。 假设从R(97)起向左进行顺序查找，得到下列新的有序序列 {R(38)，R(49)，R(65)，R(76)，R(97)} (10-6) 称从式(10-5)到式(10-6)的过程为一趟直接插入排序。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1..i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1..i]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨。在自i-1起往前有哪些信誉好的足球投注网站的过程中，可以同时后移记录。