数据结构(牛小飞)4排序比较和习题.ppt

***总结和习题习题课各种排序方法的比较本章的主要内部排序方法本章的主要内部排序方法本章研究的内部排序方法主要有：插入排序直接插入排序希尔排序交换类排序起泡排序快速排序选择类排序简单选择排序堆排序归并排序基数排序多关键字排序链式基数排序插入排序基本思想：插入排序：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。12本章的主要排序方法a.直接插入排序（基于顺序查找）常见的插入排序算法O(n2)是一种稳定的排序方法b.希尔排序（基于逐趟缩小增量）是一种不稳定的排序方法本章的主要排序方法交换类排序01基本思想：依次两两比较相邻关键字，并交换不满足排序要求的关键字，直至全部有序。02本章的主要排序方法O(n2)O(nlogn)a.起泡排序常见的交换类排序算法是一种稳定的排序方法b.快速排序是一种不稳定的排序方法本章的主要排序方法选择类排序本章的主要内部排序方法基本思想：每一趟从待排序的n-i+1（i=1,2,3,…,n-1）个记录中选出关键字最小的记录，作为有序序列中第i个记录，直到全部记录排序完毕。STEP5STEP4STEP3STEP2STEP1O(n2)是一种不稳定的排序方法O(nlogn)常见的选择类排序算法a.简单选择排序是一种不稳定的排序方法b.堆选择排序本章的主要内部排序方法归并排序本章的主要内部排序方法基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。时间复杂度为Ο(nlogn)。是一种稳定的排序方法链式基数排序基本思想：在多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，不需要进行关键字间的比较。时间复杂度为O(d(n+rd))是稳定的排序方法各种内部排序方法的比较一、时间性能各种内部排序方法的比较平均的时间性能基数排序时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为O(n2)：直接插入排序、起泡排序和简单选择排序时间复杂度为O(d(n+rd)):简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。当待排记录序列按关键字顺序有序时直接插入排序和起泡排序能达到O(n)的时间复杂度快速排序的时间性能蜕化为O(n2)。各种内部排序方法的比较指的是排序过程中所需的辅助空间大小所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；123二、空间性能各种内部排序方法的比较归并排序所需辅助空间最多，其空间复杂度为O(n);链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。0102各种内部排序方法的比较稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。排序之前:{·····Ri(K)·····Rj(K)·····}排序之后:{·····Ri(K)Rj(K)··········}三、排序方法的稳定性能各种内部排序方法的比较当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。快速排序、堆排序和希尔排序是不稳定的排序方法。对于不稳定的排序方法，只要能举出一个实例说明即可。例如:对{4,3,4,2}进行快速排序，得到{2,3,4,4}各种内部排序方法的比较关于“排序方法的时间复杂度的下限”本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法。可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制。)各种内部排序方法的比较例如:对三个关键字进行排序的判定树如下：K1K3K1K2K1K3K2K3K2K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2树上的每一次“比较”都是必要的;树上的叶子结点包含所有可能情况。各种内部排序方法的比较一般情况下，对n个关键字进行排序，可能得到的结果有n!种，由于含n!个叶子结点的二叉树的深度不小于?log2(n!)?+1,则对n个关键字进行排序的比较次数至少是?log2(n!)??nlog2n(斯蒂林近似公式)