第十章 排序.ppt

《第十章 排序.ppt》由会员分享，可在线阅读，更多相关《第十章 排序.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training第十章 排序排序定义将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序Neusoft Institute of InformationDate:25.Feb 2005IT Education&

2、Training插入排序 直接插入排序直接插入排序排序过程：整个排序过程为排序过程：整个排序过程为n-1趟插入，即先将序列中趟插入，即先将序列中第第1个记录看成是一个有序子序列，然后从第个记录看成是一个有序子序列，然后从第2个记录开个记录开始，逐个进行插入，直至整个序列有序始，逐个进行插入，直至整个序列有序Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training例49 38 65 97 76 13 27i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27

3、i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=1 ()i=7 (13 38 49 65 76 97)2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：算法描述Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training完整的插入排序算法为：public void insertSort(int r)int i,j;for(i=2；ir.lengt

4、h；i+)r0=ri;j=i-1;while(r0rj)rj+1=rj;j-;rj+1=r0;Neusoft Institute of InformationDate:25.Feb 2005IT Education&Trainingjava.io.Comparable，该接口定义了一个比较方法compareTo()方法，实现类只要用该方法实现，就可以采用下面代码对该类的对象执行直接插入排序，以升序为例：public void InsertSort(Comparable a)Comparable t;for(int i=1;i 0)/对每个待插入元素寻找插入位置if(pareTo(aj)0)if

5、(ai aj，则退出内循环break;j-;aj+1=t;Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training希尔排序希尔排序(Shell Sort)n基本思想基本思想设待排序对象序列有设待排序对象序列有 n 个对象个对象,首先取一个整数首先取一个整数 gap 0)for(i=d;i=0&RjRj+d)temp=Rj;Rj=Rj+d;Rj+d=temp;j=j-d;d=d/2;希尔排序的算法希尔排序的算法Neusoft Institute of InformationDate:25.Feb 2005IT Ed

6、ucation&Training冒泡排序冒泡排序排序思路将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止8.3 交换排序Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training2 21

7、10 08 82 25 5 4 49 9 2 25 5 1 16 62 21 14 49 92 25 5 2 25 5 1 16 6 0 08 82 21 14 49 92 25 52 25 51 16 6 0 08 82 21 14 49 92 25 5 2 25 51 16 6 0 08 82 21 14 49 92 25 5 2 25 51 16 6 0 08 8初始关键字第一趟排序第四趟排序第二趟排序第三趟排序2 21 14 49 92 25 5 2 25 51 16 60 08 8第五趟排序冒泡排序的过程冒泡排序的过程Neusoft Institute of InformationD

8、ate:25.Feb 2005IT Education&Training冒泡排序算法：public void bubble(Comparable r)int i,j,flag;Comparable temp;for(i=1;ir.length;i+)flag=0;for(j=0;jrj+1)flag=1;temprj+1;rj+1=rj；rj=temp;if(flag=0)return;Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training快速排序快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，

9、其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training快速排序的过程快速排

10、序的过程212108082525494925*25*1616初始关键字初始关键字08082525494925*25*1616212108082525494925*25*161608082525494925*25*161608082525494925*25*161608082525494925*25*16162121prikey一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成一趟排序ijijjiijji jiNeusoft Institute of InformationDate:25.Feb 2005IT Education&Training0808252549

11、4925*25*16162121完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序08082525494925*25*16162121有序序列有序序列08082525494925*25*16162121Neusoft Institute of InformationDate:25.Feb 2005IT Education&TrainingNeusoft Institute of InformationDate:25.Feb 2005IT Education&Training直接选择排序直接选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再

12、通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束选择排序Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training例初始：49 38 65 97 76 13 27 kjjjjjjtti=11349一趟：13 38 65 97 76 49 27 i=2ttjjjjj2738二趟：13 27 65 97 76 49 38 三趟：13 27 38 97 76 49 65 四趟：13 27 38 49 76 97 65 五趟：13 27 38 4

13、9 65 97 76 六趟：13 27 38 49 65 76 97 排序结束：13 27 38 49 65 76 97Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training完整算法：public void selectSort(Comparable c)int i,j,k;Comparable temp;for(i=0；ic.length；i+)for(j=i+1，k=i；jc.length；j+)if(Rj.keyRk.key)k=j；if(k!=i)temp=Ri;Ri=Rk;Rk=temp;Neusof

14、t Institute of InformationDate:25.Feb 2005IT Education&Training堆排序堆排序堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值Neusoft Institute of InformationDate:

15、25.Feb 2005IT Education&Training堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”Neusoft

16、Institute of InformationDate:25.Feb 2005IT Education&Training例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 38Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training4965502738769713输出：13 27 38766550273

17、8499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 65Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training7665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 76976

18、5762738495013输出：13 27 38 49 50 65 76 97Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training第一个问题解决方法方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选Neusoft Institute of InformationDate:25.Feb 2005IT Education&Training例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097