《数据结构》课件第八章.ppt

归并排序（二路归并）基本思想：将两个或两个以上的有序表合并为一个有序表。（两两归并）具体步骤：比较各子序列第一个记录的关键字，最小的一个就是排序后序列的第一个记录的关键字。取出该记录，继续比较各子序列现在的第一个记录的关键字，找到排序后的第二个记录时间复杂度O(n*log2n)稳定算法，但使用较少。基数排序（一）前面所介绍的排序方法都是通过交换、移动来实现的。基数排序是借助多关键字排序的思想，将单关键字按基数分为“多关键字”进行排序。多关键字的排序（多个关键字分主，次）最高位优先法（MSD法）：先按最主关键字排序，一直到按最次关键字排序后，将各组连接起来得到序列最低位优先法（LSD法）：基数排序（二）链式基数排序基本思想：分配、收集对单关键字也可按多关键字排序方法进行。拆分成多项，项的个数成为“基”（RADIX）采用LSD法进行排序具体操作：从最低位起，按关键字的不同值将序列中的记录分配到RADIX个队列中，关键字相同的在同样一链队列中，最后按关键字大小顺序链接起来稳定算法109063930589184505269008083278把每位十进制数字看成一个关键字：则k由3个关键字组成基为10e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]278109063930589184505269008083f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]930063083184505278008109589269505008109930063269278083184589个位e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]083930505184f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]063278008109589269十位e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]278930063008589184505269083f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]109008063083109184269278505589930百位各种内部排序的比较各排序时间、空间复杂度表结论：若n较小，可采用直接插入或直接选择排序当记录初始状态已经基本有序时，采用直接插入、冒泡、随机的快速排序若n较大时，采用时间复杂度为O（nlog2n）的快速排序、堆排序、归并排序；其中，快速排序时间最少，堆排序需求的辅助空间少，归并排序稳定基数排序只适用于字符串和整数这类有明显结构特征的关键字，当n较大，但d（关键字的个数）较小时使用较好小结理解排序的定义和各种排序方法的特点，并能加以灵活应用各种方法的排序过程及某些方法的时间复杂度和稳定性希尔排序、快速排序、堆排序和归并排序等高效方法是本章学习的重点和难点掌握每种排序每一趟后的排序序列*简单排序花费时间最多*时间复杂度的考虑仍然是比较次数，移动次数*排序时间复杂度——移动次数，比较次数空间复杂度——稳定性掌握每一趟的变化该算法是个稳定算法*区间减少一半！类似于折半查找*希尔取法：第一次d[0]=n/2向下取整，第二次d[1]=d[0]/2向下取整，最后一个增量为1*第一个与第二个比较，若为逆序换位，第二个与第三个比较…一趟过后最小的应该在最前边图例表示的是最大值沉，而算法表示的是最小值升*枢轴的确立，枢轴又叫控制关键字第八章内部排序内容提要基本概念插入排序快速排序选择排序归并排序基数排序排序的概述（一）排序的功能：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。排序的稳定性：如果在待排序的记录序列中有多个数据元素的关键字值相同，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，否则称之为不稳定的。原地排序：在原来占有的空间中进行，只占有少量辅助空间。排序的分类内部排序和外部排序：内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，而需要将一部分数据元素放置在内存，另一部分数据元素放置在外设上。排序概述（三）排序过程中的基本操作比较两个关键字将记录从一个位置移到另一个位置待排序序列的存储方式地址连续