第六章 排序与选择2.pptVIP

第六章 排序与选择 第六章 排序与选择 首先对排序下一个定义： 假设含n个记录的序列R为 { R1,R2,…,Rn}其相应的关键字为{K1,K2,…Kn}需确定1，2，…, n的一种排列P1,P2,…Pn,使其相应的关键字满足如下的非递减（或非递增关系） Kp1=Kp2=…=Kpn 即使序列R成为一个按关键字有序的序列 {Rp1,Rp2,…Rpn} 这样一种操作称为排序。 第六章 排序与选择 上述排序定义中的关键字Ki可以是记录Ri（i=1,2,…,n)的主关键字，也可以是记录Ri的次关键字，甚至是若干数据项的组合。若Ki是主关键字，则任何一个记录的无序序列经排序后得到的结果是唯一的；若Ki是次关键字，则排序的结果不唯一，因为待排序的记录序列中可能存在两个或两个以上关键字相等的记录。假设Ki=Kj(1=i=n,1=j=n,i!=j),且在排列前的序列中Ri领先Rj(即ij).若在排序后的序列中Ri仍领先Rj，则称所有的排序方法是稳定的；反之，若可能使排序后的序列中Rj领先Ri，则称所用的排序方法是不稳定的。 第六章 排序与选择 为了查找方便，通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以采用查找效率较高的折半查找法，其平均查找长度为log2(n+1)-1,而无序的顺序表只能进行顺序查找其平均查找长度为(n+1)/2， 如建造树表（无论是排序二叉树或B-树）的过程本身就是一个排序的过程。因此学习和研究排序方法是计算机工作者的重要课题之一。 第六章 排序与选择 由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外村进行访问的排序过程。 第六章 排序与选择 6.1、简单排序算法 1、排序问题：输入n个数a[0]、a[1]、a[2] … …a[n-1]的一个序列，要设计一个有效的排序算法，产生输入序列的一个重排，使序列元素按从小到大的顺序排列。 2、输入序列，通常是一个有n个元素的数组，当然也可以用其他形式来表示输入，如链表等。 3、在实际中，待排序的对象往往不是一个单一的数，而是一个记录，其中有一个关键字域key，它是排序的根据。 第六章 排序与选择 第六章 排序与选择 6.1.1 冒泡排序 基本思想:从第一个记录Rn开始，对每两个相邻的两个关键字Ki和Ki+1进行比较，若Ki〉Ki+1，则交换Ri和Ri+1的位置。使关键字较小的记录换至关键字较大的记录之前，使得经过一趟冒泡排序后，关键最小的记录达到最前端，接着，再在剩下的记录中找出关键字次小的记录，并把它换至第二个位置上。依次类推，一直到所有记录都有序。 第六章 排序与选择 冒泡排序的算法如下： Void BubbleSort(RecType R[ ],int n) { int i,j; RecType temp; for(i=0;in-1;i++) for( j=n-1;ji;j--) if (R[j].keyR[j-1].key) { temp=R[j]; R[j]=R[j-1]; R[j-1]=temp; } } 改进的冒泡排序算法 在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。 冒泡排序小结 1、冒泡排序比较简单，当初始序列基本有序时，冒泡排 序有较高的效率，反之效率较低；其次冒泡排序只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元； 2、冒泡排序是一种稳定的排序方法。 6.1.2 插入排序 基本思想:依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。 其具体的排序过程可以描述如下： 首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中，形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，…依此类推，每一趟都是将一个记录插入到前面的有序段中。 直接插入排序算法： 假设待排序的记录存放在数组R[0..n-1]中， 排序过程的某一中间时刻，R被划分成两个子区间， R[0..i-1]和R[0..n-1]。其中：前一个子区间是已 排好序的有序区；后一个子区间则是当前未