数据结构 排序.ppt

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

1、第第9 9章章 排序排序 1目目录录9.1基本概念基本概念9.2插入排序9.3交换排序交换排序9.5归并排序退出9.4选择排序291基本概念基本概念排排序序:是是计计算算机机程程序序设设计计中中的的一一项项重重要要操操作作，其其功功能能是是指指一一个个数数据据元元素素集集合合或或序序列列重重新新排排列列成成一一个个按按数数据据元元素素某某个个数数据据项值有序的序列。项值有序的序列。排序码排序码(关键码关键码):排序依据的数据项。排序依据的数据项。稳稳定定排排序序:排排序序前前与与排排序序后后相相同同关关键键码码元元素素间间的的位位置置关关系系，保持一致的排序方法。保持一致的排序方法。不不稳稳定

2、定排排序序:排排序序前前与与排排序序后后相相同同关关键键码码元元素素间间的的相相对对位位置置发生改变的排序方法。发生改变的排序方法。排序分为两类：排序分为两类：（1）内内排排序序:指指待待排排序序列列完完全全存存放放在在内内存存中中所所进进行行的的排排序序。内内排排序序大大致致可可分分为为五五类类：插插入入排排序序、交交换换排排序序、选选择择排排序序、归归并排序和分配排序。本章主要讨论内排序。并排序和分配排序。本章主要讨论内排序。（2）外排序：外排序：指排序过程中还需访问外存储器的排序。指排序过程中还需访问外存储器的排序。为为了了以以后后讨讨论论方方便便，我我们们直直接接将将排排序序码码写写成

3、成一一个个一一维维数数组组的的形形式式，并并且且在在没没有有声声明明的的情情形形下下，所所有有排排序序都都按按排排序序码码的的值值递增排列。递增排列。39.2 9.2 插入排序插入排序基基本本思思想想：每每次次将将一一个个待待排排序序的的元元素素，按按其其关关键键字字的的大大小小插插入入到到前前面面已已经经排排好好序序的的子子文文件件的的适适当位置，直到全部记录插入完成为止。当位置，直到全部记录插入完成为止。9.2.1 直接插入排序直接插入排序直接插入排序的基本思想是：把直接插入排序的基本思想是：把n个待排序的元素个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包看成为一个有序表和

4、一个无序表，开始时有序表中只包含一个元素，无序表中包含有含一个元素，无序表中包含有n-1个元素，排序过程中个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。适当位置，使之成为新的有序表。4例例如如，n=6，数数组组R的的六六个个排排序序码码分分别别为为：17，3，25，14，20，9。它的直接插入排序的执行过程如下：。它的直接插入排序的执行过程如下：直接插入排序举例直接插入排序举例5voidD-Insert

5、Sort(datatypeR,intn)/*待排序的待排序的n个元素放在数组个元素放在数组R中，用直接插入法进行排序中，用直接插入法进行排序*/for(i=2;i=n;i+)/*i控制第控制第i-1次插入次插入,最多进行最多进行n-1次插入次插入*/if(Ri.keyRi-1.key)/*小于时小于时,需将需将Ri插入有序表插入有序表*/R0=Ri;/*为统一算法设置监视哨为统一算法设置监视哨*/for(j=i-1;R0.keyRj.key;j-)Rj+1=Rj;/*/*元素元素后移后移*/Rj+1=R0;/*/*将放在将放在R0R0中的第中的第i i个个元素元素插入到插入到有序表有序表中中*

6、/直接插入排序算法直接插入排序算法6直接插入排序的效率分析直接插入排序的效率分析首首先先从从空空间间来来看看，它它只只需需要要一一个个元元素素的的辅辅助助空空间间，用用于于元元素素的的位位置置交交换换。从从时时间间分分析析，首首先先外外层层循循环环要要进进行行n-1次次插插入入,每每次次插插入入最最少少比比较较一一次次(正正序序),移移动动0次次;最最多多比比较较i次次(包包括括同同监监视视哨哨R0的的比比较较),移移动动i1次次(逆逆序序)(i=2,3,n)。因因此此，直直接接插插入入排序的时间复杂度为排序的时间复杂度为O（n2）。直直接接插插入入算算法法的的元元素素移移动动是是顺顺序序的的

7、，该该方方法法是是稳定的稳定的。79.2.2 9.2.2 希尔排序希尔排序(缩小增量排序缩小增量排序)希希尔尔排排序序的的基基本本思思想想：先先将将整整个个待待排排元元素素序序列列分分割割成成若若干干个个子子序序列列（由由相相隔隔某某个个“增增量量”的的元元素素组组成成的的）分分别别进进行行直直接接插插入入排排序序，待待整整个个序序列列中中的的元元素素基基本本有有序序（增增量量足足够够小小）时时，再再对对全全体体元元素素进进行行一一次次直直接接插插入入排排序序。因因为为直直接接插插入入排排序序在在元元素素基基本本有有序序的的情情况况下下（接接近近最最好好情情况况），效效率率是是很很高高的的，因

8、因此此希希尔尔排排序序在时间效率上有较大提高。在时间效率上有较大提高。8八八个个元元素素的的关关键键码码分分别别为为：91，67，35，62，29，72，46，57，希尔排序算法的执行过程为：，希尔排序算法的执行过程为：希尔排序过程举例希尔排序过程举例9希尔排序算法voidShellSort(datatypeR,intd,intt)/*按按增增量量序序列列d0、d1、d2、dt-1对对顺顺序序表表R1、R2、Rn作作希希尔尔排排序序，注意注意d0、d1、d2、dt-1除除1之外不能有公因子，且之外不能有公因子，且dt-1必须为必须为1*/for(k=0;kt;k+)ShellInsert(R,

9、dk);voidShellInsert(datatypeR,intdk)/*对顺序表对顺序表R1、R2、Rn进行一趟插入排序，进行一趟插入排序，dk为增量为增量、步长、步长*/for(i=dk+1;i=n;i+)if(Ri.key0)&(R0.keyRj.key);j=j-dk)Rj+dk=Rj;/*记录后移记录后移*/Rj+dk=R0;/*插入到正确位置插入到正确位置*/10希尔排序的效率分析虽然我们给出的算法是三层循环，最外层循环为log2n数量级，中间的for循环是n数量级的，内循环远远低于n数量级，因为当分组较多时，组内元素较少；此循环次数少；当分组较少时，组内元素增多，但已接近有序，

10、循环次数并不增加。因此，希尔排序的时间复杂性在O（nlog2n）和O（n2）之间，大致为O（n1.3）。由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。119.3交换排序交换排序主要是通过排序表中两个记录关键码的比较，若与排序主要是通过排序表中两个记录关键码的比较，若与排序要求相逆（不符合升序或降序），则将两者交换。要求相逆（不符合升序或降序），则将两者交换。9.3.1 冒泡排序冒泡排序冒冒泡泡排排序序的的基基本本思思想想：通通过过对对待待排排序序序序列列从从前前向向后后，依依次次比比较较相相邻邻元元素素的的排排序序码码，若若

11、发发现现逆逆序序则则交交换换，使使排排序序码码较较大的元素逐渐从前部移向后部。大的元素逐渐从前部移向后部。因因为为排排序序的的过过程程中中，各各元元素素不不断断接接近近自自己己的的位位置置，如如果果一一趟趟比比较较下下来来没没有有进进行行过过交交换换，就就说说明明序序列列有有序序，因因此此要要在在排排序序过过程程中中设设置置一一个个标标志志swap判判断断元元素素是是否否进进行行过过交交换换。从从而减少不必要的比较。而减少不必要的比较。120 1 2 3 4 5 6 7 849493838656597977676131327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常

12、进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交

13、换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序130 1 2 3 4 5 6 7 849384938656597977676131327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相

14、邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序140 1 2 3 4 5 6 7 849384938656597977676131327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。

15、第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65

16、、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序150 1 2 3 4 5 6 7 849384938656597977676131327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，

17、比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序160 1 2 3 4 5 6 7 849384938656597977676131327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至R

18、n个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排

19、序的方法进行用起泡排序的方法进行排序排序170 1 2 3 4 5 6 7 849384938656576977697131327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位

20、置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序180 1 2 3 4 5 6 7 849384938656576977697131327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，

21、针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序

22、190 1 2 3 4 5 6 7 849384938656576977613971327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换

23、；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序200 1 2 3 4 5 6 7 849384938656576977613971327274949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个

24、元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序210 1 2 3 4 5 6 7 84

25、9384938656576977613271327974949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行

26、交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序220 1 2 3 4 5 6 7 849384938656576977613271327974949冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，

27、针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序230 1 2 3 4 5 6 7 8493849386565769776132

28、71327499749 冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。

29、结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序240 1 2 3 4 5 6 7 8384965761327499738496576132749973849657613274997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，

30、针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序250 1 2 3 4 5 6 7 8384965761327499738496576

31、132749973849657613274997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续

32、比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序260 1 2 3 4 5 6 7 8384965761327499738496576132749973849657613274997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。

33、第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序270 1 2 3 4 5 6 7 8384965761327

34、499738496576132749973849657613274997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元

35、素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序280 1 2 3 4 5 6 7 8384965761327499738496576132749973849651376274997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1

36、个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序290 1 2 3 4 5 6 7 8

37、384965761327499738496576132749973849651376274997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则

38、继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序300 1 2 3 4 5 6 7 8384965761327499738496576132749973849651327764997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对

39、第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序310 1 2

40、 3 4 5 6 7 8384965761327499738496576132749973849651327764997冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置

41、不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序320 1 2 3 4 5 6 7 8384965761327499738496576132749973849651327497697冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第

42、 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进

43、行排序排序330 1 2 3 4 5 6 7 8384965761327499738496513274976973849651327497697冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对

44、位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序340 1 2 3 4 5 6 7 8384965761327499738496513274976973849651327497697冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个

45、元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方

46、法进行用起泡排序的方法进行排序排序350 1 2 3 4 5 6 7 8384965761327499738496513274976973849651327497697冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的

47、元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序360 1 2 3 4 5 6 7 8384965761327499738496513274976973849136527497697冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，

48、针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、2

49、7、49 用起泡排序的方法进行用起泡排序的方法进行排序排序370 1 2 3 4 5 6 7 8384965761327499738496513274976973849136527497697冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟。第 1 趟，针对第趟，针对第R1 至至Rn个个元素进行。第元素进行。第 2 趟，针对第趟，针对第 R1 至至 Rn1 个元素进行。个元素进行。第第 n-1 趟，针趟，针对第对第 R1 至至 R2 个元素进行。个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的每一趟进行的过程：从第一个

50、元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。则进行交换；否则继续比较下面两个相邻的元素。结束条件结束条件：在任何一趟进行过程中，未出现交换。在任何一趟进行过程中，未出现交换。如如:将序列将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行用起泡排序的方法进行排序排序380 1 2 3 4 5 6 7 8384965761327499738496513274976973849132765497697冒泡排序的具体过程 若若序列中有序列中有 n 个元素，通常进行个元素，通常进行 n-1 趟。第趟