内部排序-数据结构DATASTRUCTURE.pptVIP

堆排序*1）堆的定义：n个元素的序列(R1,R2,…Rn),对应的关键字序列为(k1,k2,……kn)，若此关键字序列满足下列关系，则称该元素序列为堆。或(i=1,2,…...?n/2?)ki?k2iki?k2i+1ki?k2iki?k2i+1例(96,83,27,38,11,9）例(13,38,27,50,76,65,49,97)962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值2)堆排序基本思想*堆排序在排序过程中，利用完全二叉树双亲与孩子结点的关系来选择关键字最小（或最大）的记录。基本思想：将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区为[R1,R2,…Rn]将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全二叉树按照堆定义要求进行调整，使关键字最小(大)的记录成为二叉树的根(存在R[1]中)——初建堆将根结点中记录与无序区中最后一个结点交换，并将无序区中最后一个记录划入有序区内。无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，故经过适当调整后可将无序区中记录重建成堆，无序区当前最小(大)成为根。——堆调整重复上述过程，直到无序区为空(即执行n-1次)。1如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？堆排序需解决的两个问题：方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“堆筛选”第二个问题解决方法——筛选2*第一个问题解决方法方法：依次对无序序列的第?n/2?，?n/2?-1,…,直至第1个元素作为根的子树进行堆调整。因为无序序列所对应完全二叉树的最后一个非终端结点是第?n/2?个元素，所以筛选要从第?n/2?个元素开始向上进行。4）初建堆—自下而上3）堆调整—自上而下排序过程演示：*5)算法分析*01时间复杂度：O(nlog2n)。02空间复杂度：O(1)03稳定性：堆排序是一个不稳定的排序方法。10.5归并排序(MergeSort)*归并：是将两个或两个以上的有序表合并成一个新的有序表。两路归并多路归并01归并方法：设两个有序表A和B的对象个数(表长)分别为al和bl，变量i和j分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量k是它的当前存放指针。02归并排序算法就是利用两路归并过程进行排序。其基本思想是：2）归并排序*设初始待排序序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。把这n个记录两两二路归并，得到?n/2?个有序子序列，每个子序列的长度为2或1(n为奇数)。——一趟归并排序再对?n/2?个有序子序列进行两两二路归并，……如此重复，直至得到一个长度为n的有序序列为止。课程代码：0600060课程代码：0600060数据结构(DATASTRUCTURE)计算机科学与技术学院*第十章排序概述插入排序交换排序选择排序归并排序基数排序基本概念10.1概述*排序：将一组记录按相应关键字的值递增或递减次序重新排列的过程。1关键字(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。2排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]，它们的关键字k[i]==k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。3排序方法的分类*2）排序方法的分类根据排序时使用的存储器不同，分为：内部排序:在内存实现，数据对象全部存放在内存，无内外存数据交换；适合少量数据，速度快。外部排序:排序期间全部对象太多，不能同时存放在内存，必须根据排序过程的要求，不断在内外存之间移动；适合大量数据，速度慢。按实现策略，内排序分五大类：插入排序:直接插入、shell排序交换排序：冒泡、快速排序选择排序：简单选择、树型选择、堆排序归并排序：基数排序：简单排序方法:O(n2)简单排序先进排序方法:O(nlogn)堆排序、快速排序…基数排序方法:O(dn)