九章 内部排序.pptVIP

第九章 内部排序 概 述 排序(sorting) 将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 数据表(datalist) 它是待排序数据对象的有限集合。 关键字(key) 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据，称为关键字。也称为排序码。 排序方法的稳定性 假设在对象序列中有两 个对象r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 对象r[i]排在r[j]前面。 如果在排序之后, 对象r[i]仍在对象r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 如： 待排序列: 49,38,65,97,76,13,27,49 (稳定)排序得到的序列： 13,27,38, 49,49,65,76,97 内排序与外排序 内排序是指在排序期间数据对象全部存放在内存的排序； 外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 排序的时间开销 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 内排序分类 依不同原则分 插入排序、交换排序、选择排序、归并排序、和基数排序等。 依所须工作量分 简单排序---时间复杂度O(n2) 先进排序方法---时间复杂度O(nlog2n) 基数排序---时间复杂度O(d·n) 排序过程的基本操作： 比较两个关键字的大小 将记录从一个位置移动到另一个位置 待排序记录序列的存储方式： 地址连续的一组存储单元（记录之间的次序关系由存储位置决定，实现排序必须借助移动记录） 静态链表（记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需修改指针）－－链表排序 地址连续的一组存储单元，另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中的地址，在排序之后再按照地址向量中的值调整记录的存储位置－－地址排序 插入排序 基本思想： 每步将一个待排序的对象, 按其排序码大小, 插入到前面已经排好序的一组对象的适当位置上, 直到对象全部插入为止。 直接插入排序 (Insert Sort) 当插入第i (i ? 1) 个对象时, 前面的V[0], V[1],…, V[i-1]已经排好序。这时, 用V[i]的排序码与V[i-1], V[i-2], …的排序码顺序进行比较, 找到插入位置即将V[i]插入, 原来位置上的对象向后顺移。 直接插入排序的算法 void InsertSort ( SqList L ) { //按非递减顺序对表进行排序,从后向前顺序比较 for ( i = 2; i = L.length; ++ i) if LT(L.r[i].key,L.r[i-1].key){ L.r[0]=L.r[i]; for ( j=i-1; LT(L.r[0].key,L.r[j].key); --j ) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }//if } 算法分析 设待排序对象个数为 n, 则该算法的主程序执行n-1趟。 排序码比较次数和对象移动次数与对象排序码的初始排列有关。 直接插入排序的时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。 折半插入排序 (Binary Insertsort) 既然每个要插入记录之前的纪录已经按关键字有序排列，在查找插入位置时就没有必要逐个关键字比较，可以使用折半查找来实现。由此进行的插入排序称之为折半插入排序。 折半插入排序的算法 void BInsertSort (SqList L){ for (i=2;i=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位置即为插入位置 L.r[high+1]=L.r[0]; }//for }//BInsertSort 算法分析 折半有哪些信誉好的足球投注网站比顺序有哪些信誉好的足球投注网站查找快, 所以折半插入排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序列的初始排列无关, 仅