《算法与数据结构》第8章排序及基本算法ppt.ppt

算法与数据结构,第8章 排序及基本算法,排序及基本算法,为了便于检索，人们通常希望能在计算机中保存的数据是按关键字值大小排列的有序表。 这是因为对于有序表可以采用检索效率较高的二分法检索算法，其平均检索长度为log2(n+1)-1;而对于无序表只能进行顺序检索，其平均检索长度为(n+1)/2。 又如为了方便检索，需要构造二叉检索树、B树和B+树等树表，构造这些树表的过程本身就是一个排序的过程。 在现今的计算机系统中，有相当大的一部分CPU时间开销是用于对数据的排序整理上的。 因此，学习和研究各种排序算法，分析并设计出高效适用的排序算法，是摆在计算机科学工作者面前的重要课题之一。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介,8.1 排序的基本概念,排序是数据处理中的重要运算，其功能是将一组数据元素（或记录）的任意序列，经重新排列整理成为按关键字值大小有序的序列。 排序的实际应用领域也是非常广泛的。例如在实际问题的数据处理中常会遇到这样的情况，需要把若干名字如人名、地名、国名、书名、校名、物名等按字母顺序列表；需要把若干数值如各种考试分数、田赛的长度、径赛的时间等按成绩次序排名；需要把若干不同属性的记录按照某种方法排列次序。所有这些都是排序问题，都需要把一组数据元素或记录按照某种特定的次序排列起来。,排序的基本概念（续）,排序的确切定义可以描述为： 设（R1，R2 Rn）是某文件的n个记录，其相应的关键字为（K1，K2 Kn）。 排序（sort）是这样一种操作，它确定文件中n个记录的一种排列（Rj1，Rj2 Rjn），使得其相应关键字满足递增（即不减）关系Kj1Kj2Kjn或递减（即不增）关系Kj1Kj2Kjn。 若关键字满足递增（即不减）关系时，称作按关键字升序排序(ascending sort)； 若关键字满足递减（即不增）关系时，称作按关键字降序排序(descending sort)。,排序的基本概念（续）,在前面定义中，关键字Ki(i=1，2 n)称作排序码（sort code）。 排序码可以是记录的主关键字，也可以是次关键字，或者是多个关键字的组合（即组合关键字）。 当排序码是主关键字时，由于主关键字可以惟一标识一个记录，所以排序结果是惟一的。 当排序码是次关键字时，同一关键字值可能标识了两个或两个以上的记录，所以排序结果不惟一。,排序的基本概念（续）,若相同关键字值的记录在排序前后的相对位置不会发生改变，即若Ri与Rj的关键字相同（Ki=Kj）且在排序前Ri在Rj之前，排序后的Ri仍在Rj之前，则称所用的排序算法是稳定的(stable)； 否则，若排序前后相同关键字值的记录其相对位置可能发生改变，即排序之后的序列中有可能出现Rj在Ri之前的情况，则称所用的排序算法是不稳定的。 当排序码是组合关键字时，通常称作多关键字排序，其排序结果的惟一性取决于组合关键字是否能惟一标识一个记录。,排序的分类,根据排序过程中待排序文件存放的位置不同，可以把排序分为内部和外部排序两大类。 内部排序是指待排序文件放在内存中进行排序的排序；内部排序适用于记录个数不很多的较小待排序文件的排序； 外部排序是指在待排序文件很大时，内存中不能一次容纳全部记录，还要借助于外存存放待排序文件，在排序过程中需要对外存进行访问的排序；外部排序则适用于记录个数太多不能一次全部放入内存的较大待排序文件的排序。,排序的分类（续）,按排序中所用策略的不同： 内部排序通常可以分为插入排序、选择排序、交换排序、归并排序和分配排序这五类，每一类中不同的排序算法都是基于同一策略的不同方法。 外部排序多是采用多路归并方法进行排序。,内部排序文件的组织形式,每种内部排序方法均可在不同的存储结构上实现。通常待排序文件的组织形式有三种方式： 以一维数组作为组织形式，排序过程是对记录本身进行物理重排，通过比较和判定把记录移动到合适的位置； 以链表（动态链表或静态链表）作为组织形式，排序过程中无需移动记录，仅需修改指针即可，通常把这类排序称为表排序； 为待排序文件组织一个辅助表，如组织一张含关键字和指向记录指针的索引表，在排序过程中只需对辅助表的表目进行物理重排，不需移动记录本身，在排序结束后按辅助表调整记录位置。,排序的基本概念（续）,排序的方法很多，每一种方法都有自己的优缺点，适用于在不同的环境下使用，很难说哪一种方法是最好的方法。 由于所需的辅助空间的量一般都不大，所以排序的时间代价是衡量排序算法的最重要的因素。 内部排序的时间代价主要用关键字的比较次数和记录的移动次数来衡量； 而外部排序的时间代价主要用访问外存储器的次数来衡量。,排序的基本概念（续）,在本章主要讨论内部排序算法，以记录数组作为待排序文件的组织形式，并假定关键字均为整数，按递增次序讨论排序算法（即讨论升序排序问题）。 待排序文件中记录结构类型定义如下： typedef struct int key; /*关键字*/ elemtype otheritems; /*其它域*/ recordtype /*记录类型标识符*/,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介,插入排序,插入排序的基本方法是：每次将一个待排序的记录Ri，按其关键字Ki的大小插入到前面已经排好序的部分文件中的适当位置，直到全部记录插完整个文件已排好序为止。 本节介绍的插入排序方法有直接插入排序和希尔排序；并简介二分法插入排序、二路插入排序和共享栈插入排序。,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希尔排序 8.2.3 其它插入排序简介,直接插入排序,直接插入排序（straight insertion sort）是一种最简单的排序方法。 它的基本思路是： 依次把待排序的记录逐个插入已排好序的序列中。 一开始，第一个记录是一个长度为1的有序序列； 从第二个记录起，每次用第i(i=2，3 n)个记录的关键字Ki与前面有序序列中记录的关键字Ki-1、Ki-2 K1进行比较，从而找到Ki所在记录应该插入的位置并依次后移各记录后插入之，使得有序序列的长度加1； 这样插入n-1次就会得到n个记录的有序序列，从而完成整个文件的排序工作。,直接插入排序举例,例如，已知待排序文件中记录的关键字序列为（23，48，32，107，86，75，68），直接插入排序的过程可示意如下：,其中，方括号表示已排好序的序列，i表示插入第i个记录。,直接插入排序（续）,在插入第i个记录时，用Ki和前面已排好序记录的关键字比较，若Ki小则后移一个记录，直到Ki不小于时插入位置找到了，直接插入Ki完成第i个记录的插入。 由于后移操作会覆盖第i个记录，在算法描述中可在进行第i个记录插入之前，先保存其于R0中再进行比较后移操作；这个附加的R0还可起到“监视哨”的作用，即当Ki小于前面有序序列中的每一个关键字时，在和R0中关键字（它本身）比较时不会小于，既找到了正确的插入位置，又避免了循环控制变量的越界检查。 设置监视哨是一种程序设计技巧，既使程序控制简单，又节省了测试时间提高了检索效率。,直接插入排序的算法描述,直接插入排序的算法描述如下： void insertsorting(recordtype R,int n) int i,j; for(i=2;i=n;i+) R0=Ri; j=i-1; while(R0.key Rj.key) Rj+1 = Rj; j-; Rj+1=R0; /*insertsorting end*/,直接插入排序的算法分析,在上面的算法中，外层for循环控制n-1趟插入，内层while循环完成一趟的关键字比较、记录后移和确定位置后的插入操作。 算法中的主要时间开销在于关键字的比较和记录的后移操作上。 在最好的情况下是待排序文件中各记录已经按关键字递增有序，每一趟只需一次比较操作和两次移动操作（即Ri=R0和R0=Ri）,无需记录后移；其比较次数为n-1次，移动操作次数为2（n-1）次，算法的时间复杂度为O(n)。,直接插入排序的算法分析(续),在最坏的情况下是待排序文件中各记录为关键字的逆序排列（即递减序列），每一趟中需要和前面已排好序的i-1个记录以及监视哨中R0进行关键字值的比较，即第i趟中需进行i次比较操作； 向后移动次数为i-1次，加上与监视哨之间的两次移 动，第i趟需要移动记录i+1次；总的比较次数为 次，总的移动次数为 次，算法的时间复杂度为O(n2)。,直接插入排序的算法分析(续),若初始文件中各记录是随机排列，即关键字的各种排列的出现概率相同时，我们可取上述最好与最坏情况的平均值作为比较和移动的平均次数，约为n2/4,由此可得直接插入排序的时间复杂度为O(n2)。 由于直接插入排序在整个排序过程中只需一个记录的辅助空间（即R0），所以其空间复杂度为O(1)。由于对于相同关键字值的记录在排序前后相对位置不会发生变化（如上例中的48和 ），所以直接插入排序是一种稳定的排序方法。,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希尔排序 8.2.3 其它插入排序简介,希尔排序,希尔排序（shells method），又称作缩小增量排序（diminishing increatment）。它是1959年由D.L.Shell提出来的对直接插入排序的一种改进方法。 希尔排序是不稳定的排序算法。 由直接插入排序的分析可知，在待排序文件已按关键字值递增有序时的时间复杂度为O(n)，在逆序时的时间复杂度为O(n2)。 换句话说，如果待排序文件能够基本有序，则文件中的大多数记录都不需要进行插入（即后移）操作，整个排序的时间开销就可以大大减少。 另外，当n的值很小时，n2的值受n的值的影响也不太大，直接插入排序的效率也比较高。希尔排序正是基于这两点考虑而得到的对直接插入排序的一种改进方法。,希尔排序的方法,希尔排序的方法是： 先选取一个小于n的整数d1作为第一个增量，把待排序文件中的全部记录分成d1个组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序； 然后选取第二个增量d2d1，重复上述的分组和排序工作；如此不断地选取更小的增量d3，d4 并重复上述的分组和排序工作， 直到所选取增量di=1(didi-1d2d1)时所有记录放在同一组中进行直接插入排序后为止。,希尔排序的方法（续）,希尔排序方法的一开始组数较多而组中记录较少，各组中记录的直接插入排序是处在n值很小的情况下进行，有着较高的效率；并且在不满足次序时的移动，是用较少的移动次数而得到了记录的较大移动距离。 随着di减小，组数变少组中记录个数变多的同时，组中记录也逐步变得基本有序，使得在一趟中进行直接插入排序时的效率大大地提高。 所以希尔排序始终是在较高的效率下工作。希尔排序中增量di的选择可以有不同的取法，一般是采用希尔在最早时提出的方法，即d1=,di+1=(i=2，3，4 )。 但也有人提出不同的di选取方法，如克努特（Knuth）提出的方法是d1=,di+1=(i=2，3，4 )。如何选取增量序列才能产生最好的排序效果，至今仍无法从数学角度得出圆满的结论；然而逐步缩小增量和最后一次增量为1是大家不争的事实。,希尔排序举例,设待排序文件中有10个记录，初始关键字序列为(52,38,66,87,77,16,30,62,07)，增量序列依次为5,3,1，排序过程如下：,希尔排序举例（续）,希尔排序举例（续）,第一趟排序时d1=5，把待排序文件分成五组，即（R1，R6）、（R2，R7）、（R3，R8）、（R4，R9）和（R5，R10），各组中第一个记录都自成长度为1的有序区，依次把各组的第二个记录插入有序区中得到第一趟排序结果； 第二趟排序时d2=3，把待排序文件分成三组，即（R1，R4，R7，R10）、（R2，R5，R8）和（R3，R6，R9），对各组进行直接插入排序后得到第二趟排序结果； 第三趟排序时d3=1，整个待排序文件为一组，对整个文件做直接插入排序得到的第三趟排序结果，使整个待排序文件按关键字值有序，即得到最终的排序结果。,希尔排序的算法描述(不设置监视哨),若不设置监视哨，希尔排序的算法可描述如下： void shellsorting(recordtype R,int n) int i,j,d; d = n; do d = (d+1)/2; for(i = d+1;i d) /*shellsorting end*/,希尔排序（续）,需要说明的是，算法中没有调用直接插入排序算法insertsorting，而是独立设计直接插入排序的部分；这是因为希尔排序中距离为d的倍数的记录为一组，组中成员记录之间有间隔不连续不能直接调用的缘故。 另外，在for循环中的分组执行直接插入排序的过程，是依次先插入d个组中的第二个记录，再插入d个组中的第三个记录最后插入d个组中的最后一个记录；是d个组的交替插入过程，而不是一个组的直接插入排序完成后再进行下一组，这样有利于算法设计的简洁性和算法描述的方便性。,希尔排序（续）,如果考虑设置监视哨，很自然地会考虑到仿照直接插入排序算法中的监视哨设置办法。对于增量为d的一趟希尔排序，待排序文件被分成d 组，各组中记录之间的距离为d；需要在R1到Rd处设置监视哨，而在Rd+1到Rd+n处安排待排序文件中的n个记录。由于在各趟排序中的增量d1,d2 di是逐次缩小的，而待排序文件中各记录的位置空间安排好之后不宜变动（移动需时间开销），所以d可选为di中的最大值d1，即一次性安排监视哨空间并固定不变； 另外，监视哨中的值应在不同组中的不同记录插入时安排不同的值（即待插入记录的值），但是多次更换监视哨中的值既繁琐又影响效率，我们可以考虑在排序之前一次性设置各监视哨的值，可设置为不超过待排序文件中最小关键字值的某一个值如-maxint。这种监视哨的设置方法，没有在监视哨中保存各组中的一个个待插入记录，但可以统一保存待插入记录于R0中。,希尔排序的算法描述(设置监视哨),设置监视哨的希尔排序算法可描述如下： void shellsort(recordtype R,int n) int i,j,d; for(i=1;i 1); /*shellsort end*/,希尔排序的算法分析,在前面给出的两个算法，除了是否设置监视哨外，排序的方法是相同的，其时间复杂度也是相同的；其增量序列为d1= ，di= (i2)。算法中的主要时间开销在于三重循环： 外层do-while循环控制排序趟数，共执行log2n次。 中层的for循环控制一趟中各组记录的直接插入排序，执行次数依次为 次；其平均次数为 ；即中层for循环的平均执行次数不超过n。 内层的while循环确定各组中每个记录的插入位置，进行关键字的比较和记录的移动操作；,希尔排序的算法分析（续）,在最好的情况下只执行一次比较而无记录移动，其一趟中总的比较次数与中层for循环的执行次数相同，为 ； 而一趟中执行插入的次数为n-di，即平均比较次数不超过 ,更不会超过log2n次； 由于希尔排序算法中开始时两个记录一组，以后随着组数的减少组中记录增多也逐步基本有序，所以在n较大时的其它情况下的平均比较次数也是接近于最好情况下的次数log2n或是它的线性函数，而移动次数或平均移动次数是远远小于比较次数和平均比较次数的； 由此得内层while循环的平均执行次数为O(log2n)阶函数。由算法分析的乘法法则可知，前面给出的两个希尔排序算法，shellsorting和shellsort的时间复杂度为O(n(log2n)2)。,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希尔排序 8.2.3 其它插入排序简介,1.二分法插入排序,由第七章的讨论我们知道，对有序表采用二分法检索，检索性能大大优于顺序检索。 如果我们把直接插入排序中的由后向前顺序检索寻找插入位置的方法改为用二分法检索来实现，当n较大时就可以大幅度地降低关键字的比较次数。我们把经过这种改进后的插入排序方法，称作二分法插入排序（binary insertion sort）。 二分法插入排序与直接插入排序相比较，仅是减少了寻找插入位置时的关键字比较次数，记录的移动次数没有改变，其时间复杂度仍为O(n2)； 所需的辅助存储空间也与直接插入排序相同，也是稳定的排序方法（在检索位置出现关键字值相等时需后移插入位置指示器变量，否则为不稳定方法）。,2.二路插入排序,二路插入排序（2-way insertion sort）是在二分法插入排序基础上的进一步改进，改进的目标是减少排序过程中记录的移动次数，但为此多开销了n个记录大小的辅助存储空间。 其具体方法是： 另设一个和R同类型的数组S，先将R1赋给S1，并将S1看成是在已排好序序列中处于中间位置的记录； 然后从R中第二个记录起，依次插入到S1之前或S1之后的有序序列中去， 若待插记录的关键字小于S1.key则插入S1之前的有序表中，否则插入S1之后的有序表中。 在算法实现时，把S数组看成是一个循环数组，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在S中的位置。,二路插入排序举例,二路插入排序举例（续）,二路插入排序（续）,在二路插入排序中，记录的移动次数约为n2/8，比直接插入排序减少移动次数约一半。它只能减少移动次数而不能绝对避免移动记录，若要大幅度降低移动次数，可改变存储结构为静态链表，进行表插入排序。 此外，二路插入排序中，当R1为待排序文件中最小或最大关键字的记录时，完全失去优越性退化为直接插入排序的时间效率。 二路插入排序，是一种稳定的排序方法。,3.共享栈插入排序,共享栈插入排序（shared stack insertion sort）也是对直接插入排序的一种改进方法。 其基本思想是： 把待排序的记录数组R看作是一个静态的共享栈（栈1和栈2），栈1按数组下标由小到大方向增长，栈2按数组下标由大到小方向增长；栈1中按关键字升序排列压入待排序记录，栈2中按关键字降序排列压入待排序记录。 一开始先比较R1和Rn的关键字值大小，若R1Rn则交换；top1=1,top2=n； 然后把R2到Rn-1逐一插入两个栈中，插入的过程中始终保证栈1的栈顶记录的关键字值都不大于栈2 的栈顶记录的关键字值。,共享栈插入排序（续）,为此需要区分以下三种情况并作相应处理： 当待插入记录Ri的关键字值不小于栈1 的栈顶记录的关键字值且不大于栈2的栈顶记录的关键字值时，将待插记录压入栈1中。即Ri.keyRtop1.key且Ri.keyRtop2.key时进栈1，只须改变top1的值为top1+1即可。 当Ri.keytop2.key时，由栈2反复传送记录到栈1，直到Ri.keytop2.key时将Ri插入栈2。由栈2传送到栈1一个记录，需要把Ri+1到Rtop2-1的记录后移一个位置。,共享栈插入排序举例,共享栈插入排序举例（续）,共享栈插入排序（续）,共享栈插入排序不需要增加额外的存储开销，在时间性能上与二路插入排序相当，而且有效地避免了因R1为待排序记录中关键字值为最大或最小记录时完全失去优越性的不足。 若增加存储开销另设与R相同类型的数组作为共享栈，则可以进一步减少移动次数，且排序结果不象二路插入排序那样要使用循环数组解释。 共享栈插入排序是一种稳定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介,交换排序,交换排序的基本方法是，两两比较待排序记录的关键字值，并交换那些不满足顺序要求的记录对，直到全部待排序记录都已满足顺序要求时为止。 本节介绍两种交换排序的方法： 一种是冒泡排序， 一种是快速排序。,8.3 交换排序,8.3.1 冒泡排序 8.3.2 快速排序,冒泡排序,冒泡排序（bubble sort）也称作起泡排序，是一种简单的排序方法。 它是通过相邻记录之间的关键字比较和记录交换，使关键字值较小的记录由底部向上移动，而关键字值较大的记录由顶部向下移动，就象水中的气泡向上飘浮（冒泡）一样。,冒泡排序算法,冒泡排序的具体做法是： 将关键字纵向排列，然后自下而上地对相邻两个记录的关键字进行比较，若为逆序（即Rj-1.keyRj.key，j=n,n-12）则交换两个记录，直到全部记录都比较和交换完毕（即j=2），第一趟冒泡排序结束； 此时最小关键字值的记录上浮到了R1的位置上。然后对n-1个记录重复类似的操作，次小关键字值的记录上浮到R2的位置上。 重复进行这样的过程，直到没有记录需要交换为止（最多需n-1趟冒泡排序），整个待排序文件就按关键字值升序排列完毕。,冒泡排序算法举例,例如，对于8个记录的关键字序列（46，26，43，18，74，21, ,57），冒泡排序的过程如下图所示：,冒泡排序算法（续）,由该冒泡排序的实例，也证实了至多需要n-1趟冒泡排序即可完成整个排序。 事实上存在不需要n-1趟就可以完全排好序的情况，如上例的第五趟排序后就已经排好序了； 其识别办法是，若某一趟冒泡排序过程中没有进行记录的位置交换，则说明待排序文件已经完全排好序了。 为此，需在算法中引入一个交换状态变量flag，在每一趟排序之前置flag为0，每次交换时给flag加1，若一趟结束时flag为0则终止算法。,冒泡排序的算法描述,void bubblesort(recordtype R,int n) int i,j,flag; recordtype temp; for(i=1;i= i+1;j-) if(Rj-1.key Rj.key) temp=Rj-1; Rj-1=Rj; Rj=temp; flag=flag+1; /*置已交换标志*/ if(flag=0) break; /*bubblesort end */,冒泡排序算法分析,冒泡排序也是一种稳定的排序方法。 其时间复杂度可以如下分析： 在最好的情况下，是初始记录的关键字已递增有序时，只需一趟排序，比较次数为n-1，没有交换记录即记录的移动次数为0； 在最坏的情况下，是初始记录递减有序（即逆序）时，需进行n-1趟排序，比较次数为 ，交换次数为 ，每次交换需三次移动记录，其移动次数为 。 在平均情况下，关键字的比较次数和记录的移动次数大约为最坏情况下的一半，因此冒泡排序算法的时间复杂度为O(n2)。,冒泡排序算法分析（续）,上述的冒泡排序算法还可以作一些改进来提高排序速度，比如： 在每趟排序中记住最后一次发生交换记录的位置K，因为位置K之前的记录都已排好了序，下一趟的排序可以终止于位置K而不必进行到预定的下界位置i。 在排序过程中交替变化扫描比较的方向，即前一趟由后向前扫描，后一趟则由前向后扫描，而不是一直都由后向前扫描。由后向前扫描比较交换一趟，可使最轻的气泡上浮到顶部，但只能使最重的气泡下沉一个位置；由前向后扫描比较交换一趟，可使最重的气泡下沉到底部，但只能使最轻的气泡上浮一个位置。交替变化扫描方向可以加速最轻和最重的气泡向两端迅速沉浮，有利于加速排序过程。,8.3 交换排序,8.3.1 冒泡排序 8.3.2 快速排序,快速排序,快速排序（quick sort）也称作分区交换排序，是对冒泡排序的一种改进排序方法。它是目前各种内部排序方法中较快的方法，故称之为快速排序。 快速排序的基本思想是： 在待排序文件的n个记录中，任取一个记录（通常是选取第一个记录）作为基准； 经过一趟排序后以基准记录的关键字把全部记录分为两部分，所有关键字值比基准记录关键字值小的记录都排列在基准记录之前，而所有关键字值比基准记录关键字值大的记录都排列在基准记录之后； 然后对基准记录前后的这两个部分分别重复这样的过程，得到本趟排序的两个新到位的基准和四个部分如此重复上述过程，直到每一个部分只剩下一个记录（即全部到位）时为止。,快速排序算法,设两个指示器变量i和j，分别指向待排序区间的第一个记录和最后一个记录； 先将第一个记录移到暂存变量temp中，然后j从区间的最后一个记录起向前扫描，直到找到满足Rj.keytemp.key的记录时，将Ri移入Rj中； 就这样j自j-1从后向前扫描一次移入一个Rj于Ri中，i自i+1从前向后扫描一次移入一个Ri于Rj中，反复交替的扫描和移动记录； 直到i=j时把temp移入Ri中（区间中第一个记录应在的位置），它把整个待排序区间分割为相互独立的两个更小的区间。,快速排序的算法描述,这种把一个待排序区间通过基准记录（第一个记录）分割成为两个区间的一次分割排序算法如下： int divideareasort(recordtype R,int s,int t) int i,j; recordtype temp; i=s; j=t; temp=Rs; do while(Rj.key=temp.key),快速排序的算法描述（续）,while(Ri.key=temp.key) /*divideareasort end*/,快速排序的算法描述（续）,对于待排序文件R利用一次分割区间排序算法时，令s=1和t=n即可完成第一趟排序；由此得到的两个更小的区间R1i-1和Ri+1n，继续利用算法divideareasort分割为更小的四个区间；如此一直进行下去，直到都分割为只有一个记录时排序结束。调用divideareasort对R 进行快速排序的递归算法可描述如下： void quicksort(recordtype R,int s,int t) int i; if(st) i=divideareasort(R,s,t); quicksort(R,s,i-1); quicksort(R,i+1,t); /*quicksort end*/,快速排序的算法举例,下面我们使用快速排序算法对关键字序列（36，73，65，97，13，27， ，29）排序，在下面的排序过程示例中，先给出第一趟中的区间分割的整个过程，然后给出各趟的排序结果；用方括号表示区间，用方框表示暂存变量temp的关键字值（并未参加交换，在分割完成后才放入最终位置上）。,快速排序的算法举例（续）,快速排序的算法举例（续）,快速排序的算法举例（续）,快速排序的算法分析,快速排序过程中各趟中所选择的基准可以用一棵二叉树来表示，如上例中的基准二叉树如右图所示。基准二叉树反映了快速排序的递归调用过程，也便于我们对快速排序算法进行性能分析。,快速排序的基准二叉树是关键字的一棵二叉检索树，其中序遍历序列就是关键字的升序排列。 在最好的情况下，基准二叉树是一棵理想的平衡二叉检索树，深度为 ，递归所需栈的存储开销为O(log2n)，时间开销为结点数乘平均检索长度，即O(nlog2n)。,快速排序的算法分析（续）,在最坏情况下，基准二叉树是一棵单枝二叉检索树，深度为n，存储开销为O(n)，时间开销为O(n2)。 在平均情况下，基准二叉树是一棵随机的二叉检索树，由于二叉检索树的平均检索长度为O(log2n)，故时间开销也是O(nlog2n)。 为了避免初始关键字序列有序或基本有序时快速排序蜕化为冒泡排序（即基准二叉树为单枝或近似单枝二叉树）的情况，通常采取“三者取中”的基准记录选取办法改进之。 所谓三者取中是指在Rs、Rt和R(s+t)/2三者中选取关键字值居中的记录作为分割区间的基准，这种选取基准记录的方法可以大大改善快速排序在最坏情况下的性能。 快速排序算法是一种不稳定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介,选择排序,选择排序的基本方法是，每次从待排序文件的各个记录中，依次选出关键字值最小的记录放在已排好序的序列中，直到选完为止。 本节介绍： 直接选择排序 树型选择排序 堆排序。,8.4 选择排序,8.4.1 直接选择排序 8.4.2 树形选择排序 8.4.3 堆排序,直接选择排序,直接选择排序（direct selection sort）也称作简单选择排序。 其具体做法是： 对于待排序文件R1.n，通过比较首先选出关键字值最小的记录与R1交换， 然后在其余记录中选出次小关键字的记录与R2交换 如此进行n-1次的选择与交换，R1.n中所有记录就按关键字升序次序排列完毕。,直接选择排序举例,直接选择排序的过程可示例如下：,直接选择排序举例（续）,直接选择排序的算法描述,直接选择排序的算法可描述如下： void selectsort(recordtype R,int n) int i,j,m; recordtype temp; for(i=1;i=n-1;i+) m=i; for(j=i+1;i=n;j+) if(Rj.keyRm.key) m=j; if(m!=i) temp=Ri; Ri=Rm; Rm=temp; /*selectsort end*/,直接选择排序的算法分析,直接选择排序只需要一个记录大小的辅助存储空间用于记录交换，其空间复杂度为O(1)。 在排序过程中至多进行n-1趟排序，即至多交换记录n-1次，做3(n-1)次记录移动；然而不论初始状态如何，在每一趟中都需要和所有记录的关键字进行比较； 为了选出第i趟的最小关键字，需要的比较次数为n-i，总的比较次数为 。由此得到直接选择排序的时间复杂度为O(n2)。 由于在直接选择排序中存在着任意位置上的记录互换的可能性，所以有可能改变具有相同关键字值的记录的相对位置次序，如（5, ,2）的直接选择排序结果为（2, ,5）； 因此直接选择排序方法是不稳定的。,8.4 选择排序,8.4.1 直接选择排序 8.4.2 树形选择排序 8.4.3 堆排序,树形选择排序,树形选择排序（tree selection sort）也称作锦标赛排序（tournament sort），这种排序方法是按照锦标赛的思路进行的。 锦标赛是将n个参赛选手两两之间进行比赛（余下的一个轮空直接进入下一轮比赛），胜出者再两两之间比赛，经过 轮比赛后产生出第一名。 树形选择排序是将待排序的n个记录的关键字作为完全二叉树的叶子结点，依次两两之间比较，关键字值小者作为其双亲结点，最后若余下一个则轮空参加下一轮比较；然后对得到的这些双亲结点再两两之间比较产生其双亲结点（小者）如此经过 轮比较后，关键字值最小的记录就在根结点位置。,树形选择排序举例,选择关键字值最小的记录放在根结点位置的过程如下图(a)的二叉树所示。接下来将最小关键字值改为，然后沿该结点到树根的路径依次进行各分枝结点子女之间的比较，上升到根结点的是次小关键字值的记录，如下图(b)所示；如此继续进行下去，直到所有记录都已选出时为止。,树形选择排序算法分析,在树形选择排序中，除第一次选出最小关键字需n-1次比较外，选出次小关键字和其它关键字都需经过从叶到根的路径，即需进行 次比较。 总的比较次数至多为 ，所以其时间复杂度为O(nlog2n)。 树形选择排序的缺点是需要的辅助空间较多，需要用n-1个记录大小的空间来保存各层次的比较结果；此外，与进行多余的比较也是其缺点之一。,8.4 选择排序,8.4.1 直接选择排序 8.4.2 树形选择排序 8.4.3 堆排序,堆排序,为了克服树形选择排序需要较多辅助空间保存比较结果和与进行多余比较的缺点； 在1964年威洛姆斯（J.Willioms）和弗洛伊德（Floyd）对树形选择排序进行了改进，提出了新的排序方法堆排序（heap sort）方法，使其比较次数达到树形选择排序的水平，同时又不会增加额外的存储开销，只需一个记录大小的空间用于记录间的交换。,堆的定义,堆的定义为，对于一个关键字序列（k1，k2 kn），当且仅当对于所有的i=1，2，都满足下面的关系或都满足下面的关系时，称之为堆； 都满足关系时称之为最小值根堆； 都满足关系时称之为最大值根堆。 如果将与此序列对应的一维数组看成是一棵完全二叉树，则堆的含义表明完全二叉树中任一非终端结点上的数据值均不大于（或不小于）其左孩子和右孩子结点的值。 因此在一个堆中，堆顶元素（完全二叉树的根）必为堆中的最小（或最大）元素，并且堆中的每一棵子树也都是堆。,堆排序举例,例如关键字序列（12，15，35，25，39，67）和序列（75，38，62，28，18，49）都是堆，前者是最小值根堆而后者是最大值根堆，其对应的完全二叉树分别如下图的(a)和(b)所示。,堆排序的基本思想,堆排序的基本思想是，对待排序文件中的n个记录，依它们的关键字值大小按堆的定义排成一个序列（称之为建堆），从而输出堆顶的最小关键字（用最小值根堆排序）的记录，然后对剩余的关键字再次建堆，便得到次小关键字的记录，如此反复进行输出和建堆，直到全部记录按关键字排成有序序列时为止。 由以上分析可知，要实现堆排序需要解决如下两个问题： 如何由关键字值的无序序列建成一个堆？即建初始堆问题； 如何在输出堆顶记录之后调整剩余记录为一个新堆？即堆调整问题。,创建初始堆,先讨论建初始堆问题。在1964年弗洛伊德（Floyd）提出了筛选法，其具体方法是 将待排序记录的关键字分放到一棵完全二叉树的各个结点中，此时的完全二叉树一般不具备堆的特性。 然而所有i 的结点Ki都没有孩子结点，以这样的Ki为根的子树已经是堆了； 因此建初始堆可以从完全二叉树的最后一个分枝结点Ki(i= )开始，通过调整逐步使以Ki、Ki-1、K1为根的子树满足堆的定义，直到以K1为根的树满足堆定义时初始堆建成。,创建初始堆（续）,在对Ki（i= ， -1 1）为根的子树建堆的过程中，可能需要对记录的位置进行调整； 若在调整过程中使下一层已建成堆的子树不满足堆的定义，则要继续向下层进行调整，直到某一个下层满足堆的定义时为止，最坏的情况下是这种调整可能一直延伸到树的叶子结点。 这种方法就像过筛子一样，把最小关键字值的记录一层一层地筛选出来，最后输出堆顶的最小关键字记录。,建初始堆（最小根堆）过程举例,下图给出了完全二叉树表示的一组关键字值建初始堆的示例，所用关键字序列为（47，33，61，82，72，11，25， ）；由于n=8，故从第4个结点开始进行调整。,建初始堆(最小根堆)过程举例(续),堆排序过程举例,现在讨论堆调整的问题。在输出堆顶记录之后，用堆中的最后一个记录替代原堆顶记录。 由于除根结点K1之外的所有子树仍然具有堆的性质，故只需要对根结点自上而下调整即可。 例如对上例所给的关键字序列，经初始建堆后得到图(a)所示的堆，同时得到堆顶的最小关键字11所在的记录； 然后输出堆顶记录（key=11）并用最后一个记录（key=82）替代堆顶，如图(b)所示。此时由于以K2和K3为根的子树仍具有堆的特性，只需对根自上而下按堆的定义调整。 首先将堆顶元素K1与左右孩子K2和K3比较，若K1 K2且K1 K3不需调整已满足堆定义；否则选择K2和K3中关键字值小的记录与堆顶记录交换。,堆排序过程举例（续）,由于K3K2且K3K1，则82与25所在的两个记录交换位置； 又由于交换破坏了右子树的堆，则需再次进行类似的调整，直至进行到叶子结点； 调整后的状态如图 (c)所示，即得到一个有n-1个记录的新堆，同时得到次小关键字25所在的记录。 反复重复以上过程，即可实现上例所给关键字序列所对应的待排序文件的堆排序，其堆排序过程如下图所示。,堆排序过程举例（续）,堆排序过程举例（续）,堆排序过程举例（续）,由前面的讨论我们知道，堆调整是从根结点向下的一个筛选过程； 而建初始堆是从最后一个分枝结点开始到根结点结束的多次向下的筛选过程。 所以设计一个筛选算法，完成对Rs.t（只有Rs不满足堆特性，其它结点均满足堆特性）进行筛选是至关重要的。,筛选算法的算法描述,void heapadjust(recordtype R,int s,int t) int i,j; recordtype temp; temp=Rs; i=s; j=2*i; while(jRj+1.key) j+; if(temp.keyRj.key) Ri=Rj; i=j; j=2*i; else j=t+1; Ri=temp; /*heapadjust end*/,堆排序的算法描述,有了上述调整堆的筛选算法，就可以很方便地设计完整的堆排序算法如下： void heapsort(recordtype R,int n) int i; recordtype temp; for(i=n/2;i=1;i-) heapadjust(R,i,n); for(i=n;i1;i-) temp=R1; R1=Ri; Ri=temp; heapadjust(R,1,i-1); /*heapadjust end*/,堆排序的算法分析,堆排序的性能分析如下：设表示堆的完全二叉树深度为h，h= ，从根到叶的筛选过程中，关键字的比较次数至多为2（k-1）次，至多交换记录k次。所以在建好堆后，排序过程的n-1次筛选中的比较次数不会超过下式的值： 而在建立初始堆时的比较次数不会超过4n次，因此堆排序在最坏情况下的时间复杂度为O(nlog2n)。 此外，堆排序所需的辅助存储空间少。 堆排序是一种不稳定的排序方法。 堆排序适宜用于待排序文件中记录较多的情况，因为其主要时间开销在于建堆和调整堆，记录较少时不合算。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介,归并排序,归并排序（merge sort）的基本思想是： 将一些已排序的子文件进行合并而得到一个完整的有序文件。 归并时只要比较各子文件的第一个记录的关键字，其最小者就是全局最小者；取出它后继续比较各子文件的第一个记录的关键码，就可以得到全局的次小者如此下去就可完成排序任务。 假设待排序文件中含有n个记录，我们可以把它看作是n个有序的子序列，每个有序子序列的长度为1；然后两两归并得到个长度为2（其中最后一个长度可能为1）的有序子序列；再两两归并得到长度为4的若干有序子序列如此这样反复归并，直到得到一个长度为n的有序序列时为止。这种排序方法称为二路归并排序（two-way merge sort）。,归并排序举例,例如，对于待排序文件的关键字序列（22，36，06，78，25，43，73，18，39，62，27，66，13），利用二路归并排序的过程如下：,归并排序举例,由上述归并排序过程可以看出，二路归并的主要操作是把相邻两个有序序列归并成为一个有序序列；对于n个记录的待排序文件，需要归并趟才能完成排序；每趟归并使有序子序列的长度增加一倍，而使有序子序列的个数减少约一半。 下面，我们给出对相邻两个有序序列的归并算法，并给出归并排序的递归算法和非递归算法。,8.5 归并排序,8.5.1 归并相邻两个有序序列 8.5.2 二路归并排序的递归算法 8.5.3 二路归并排序的非递归算法,归并相邻两个有序序列,在前面分析的基础上，归并相邻两个有序序列为一个有序序列的算法merge可描述如下： void merge(recordtype R,int L,int m,int h,recordtype R1) int i,j,k; i=L; /*i指向第一个有序子序列的第一个记录*/ j=m+1; /*j指向第二个有序子序列的第一个记录*/ k=L; /*k指向结果有序序列的第一个位置*/ while(i=m),归并相邻两个有序序列（续）,while(im，要么jh，使得最后的两个while循环总有一个相当于空语句，而另一个while循环把剩余记录传送到R1中。,8.5 归并排序,8.5.1 归并相邻两个有序序列 8.5.2 二路归并排序的递归算法 8.5.3 二路归并排序的非递归算法,二路归并排序的递归算法,在前述算法merge的基础上，可给出二路归并排序的递归算法如下： void mergesortrecalg(recordtype R,intL,int h,recordtype R1) int m; if(L=h) R1L=RL; else m=(L+h)/2; mergesortrecalg(R,L,m,R1); mergesortrecalg(R,m+1,h,R1); merge(R1,L,m,h,R); /*mergesortrecalg end*/ 对待排序文件R1.n中的n个记录排序，只须用参数R、1、n调用该递归算法，即mergesortrecalg(R,1,n,R1)即可。,8.5 归并排序,8.5.1 归并相邻两个有序序列 8.5.2 二路归并排序的递归算法 8.5.3 二路归并排序的非递归算法,二路归并排序的非递归算法,在给出二路归并排序的非递归算法之前，我们先讨论一趟归并排序的实现算法。 设R1.n中的有序子序列长度为len，只有最后一个有序子序列的长度有可能小于len，进行两两有序的子序列归并后的结果依次存放在R11.n中。 进行一趟归并排序时调用算法merge，依次对相邻的两个长度为len的有序子序列归并；当有序子序列为奇数个或虽为偶数个但最后一个有序子序列长度小于len时的两种情况做特殊处理。,二路归并排序的非递归算法(续),一趟归并排序算法可描述如下： void mergepass(recordtype R,int len,int n,recordtype R1) int i=1; while(i+2*len-1=n) merge(R1,i,i+len-1,i+2*len-1,R1); i=i+2*len; if(i+len-1n) merge(R,i,i+len-1,n,R1); else while(i=n) R1i=Ri; i+; /*mergepass end*/,二路归并排序的非递归算法(续),在一趟归并排序的基础上，可以很方便地得到二路归并排序的非递归算法如下： void mergesort(recordtype R,int n) int len=1; recordtype R1; while(lenn) mergepass(R,len,n,R1); len=2*len; mergepass(R1,len,n,R); len=2*len; /*mergesort end*/,二路归并排序的算法分析,如果把待排序文件R中的n个记录看作叶子结点，把两两归并得到的有序子序列看成是两个归并对象有序子序列的双亲结点，则归并过程对应由叶向根生成一棵二叉树的过程，所以归并排序的趟数为 ； 而每趟归并需移动记录n次（关键字比较约n次），由乘法准则知二路归并排序的时间复杂度为O(nlog2n)。 由于二路归并排序过程中需要一个与待排序文件大小相同的辅助数组，所以其空间复杂度为O(n)。 二路归并排序是一种稳定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法的比较和选择 8.8 外部排序简介,二路归并排序的算法分析,前面介绍的各种排序方法，都是通过对待排序文件中记录的关键字值大小的比较来进行的。 基数排序（radix sort）方法则不同，它不用进行关键字值的大小比较，而是借助于多关键字排序的思想，通过对待排序记录按单逻辑关键字进行分配和收集来实现的一种排序方法。,8.6 基数排序,8.6.1 多关键字排序 8.6.2 链式基数排序,多关键字排序,我们先通过一个大家都熟悉的整理扑克牌的例子来说明多关键字排序的思想和方法。 扑克牌有两个关键字，即花色和点力；其次序定义为 花色：梅花方块红桃黑桃 点力：2345678910JQKA 并且花色的优先级别高于点力，即高一级花色的最小点力2大于低一级花色的最大点力A。 因此，要比较任意两张扑克牌的大小，方法是先比较花色，若花色相同时再比较点力。,多关键字排序（续）,如果要根据上述关系把一幅扑克牌整理为升序次序，即梅花2、梅花3 梅花A、方块2 方块A、红桃2 红桃A、黑桃2 黑桃A的次序，通常有如下两种整理方法： 先按花色分成四堆，然后再按点力把每堆整理有序，最后按花色由低级花色到高级花色叠加在一起。 先按点力分成十三堆，然后按点力由小到大的顺序收集在一起；再按花色不同分成四堆，最后按花色顺序收集起来。,多关键字排序（续）,前面两种理牌的方法便是两种多关键字排序的方法。上述的例子可以推广到一般情况下： 设待排序文件R的n个记录（R1,R2 Rn）中，每个记录Ri都含有d个关键字位（ ），称其中两个记录有序（即RiRj）是指满足条件 ； 若对于任意记录都满足RiRj（1ijn），则称待排序文件R有序；利用d个关键字位整理待排序文件R有序的过程，称作多关键字排序。,多关键字排序（续）,多关键字排序的方法通常有两种： 最高位优先法（most significant digit first），简称MSD法。 它是先按最高关键字位 对待排序文件中的n个记录排序，把待排序文件中n个记录分为若干堆，每个堆中都具有相同的 值； 然后在各个堆中再按关键字位 进行排序，每个堆中的记录又按 的值分成若干更小的堆 如此不断地按d个关键字位把较大地堆分为较小的堆，直到用 对各个堆排序后，各个堆中的记录依次排在一起便形成一个有序文件。,多关键字排序（续）, 是低位优先法（least significant digit first），简称LSD法。 它是先按最低关键字位 对待排序文件中的n个记录进行排序，按 的值把待排序文件中的n个记录分配到具有不同 值的若干个堆， 然后按 值从小到大的次序收集在一起；下一次再按高一位关键字位 的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集； 直到用 分配和收集之后，整个文件按多关键字位 有序。,多关键字排序（续）,显然前述的扑克牌排序中， 第一种理排过程采用的是最高位优先法（MSD法）， 而第二种理牌过程是采用最低位优先法（LSD法）。 通过对上述两种方法的比较可以看出其不同的特点： MSD法排序，是将待排序文件中所有记录分成若干独立的子堆，每个堆中记录的排序是独立进行的； 而LSD 法排序时将待排序文件中所有记录分成的若干子堆不独立，堆中记录的排序不能独立进行，需要进行d趟的分配和收集来完成整个文件中记录的排序。,8.6 基数排序,8.6.1 多关键字排序 8.6.2 链式基数排序,链式基数排序,基数排序就是按照LSD法，对待排序文件中各记录用单逻辑关键字进行分配和收集的一种排序方法。 假设含有n个记录的待排序文件中，每个记录的关键字由d 个关键字位 组成，并且每个关键字位的取值范围都相同，即c1 crd（1jd）； 关键字位可能的取值个数rd称为基数。基数的选择和关键字位的分解因关键字的类型而异。 若关键字是十进制整数时，则基数rd为10，c1=0，c1