冒泡法排序原理.ppt

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

1、经典算法介绍：经典算法介绍：排序问题是程序设计中的典型问题之一，它有很广泛排序问题是程序设计中的典型问题之一，它有很广泛的应用，比如给你一组学生成绩，要你输出前的应用，比如给你一组学生成绩，要你输出前2 0 名的成绩。名的成绩。这时你就要用到排序。再比如要问你中国的这时你就要用到排序。再比如要问你中国的GDP排世界第排世界第几，你要先把各国几，你要先把各国GDP排个序，才知道中国在第几。排个序，才知道中国在第几。所谓排序就是将数组中的各元素的值按从小到大的顺所谓排序就是将数组中的各元素的值按从小到大的顺序或按从大到小的顺序重新排列。序或按从大到小的顺序重新排列。排序过程一般都要进行元素值的比较

2、和元素值的交换。排序过程一般都要进行元素值的比较和元素值的交换。冒泡法排序冒泡法排序冒泡法原理冒泡法原理分析分析分析分析:假设有假设有假设有假设有N N个数据放在数组个数据放在数组个数据放在数组个数据放在数组a a中中中中,现要把这现要把这现要把这现要把这N N个数从小到大排序个数从小到大排序个数从小到大排序个数从小到大排序.冒泡排序法的基本思想是冒泡排序法的基本思想是冒泡排序法的基本思想是冒泡排序法的基本思想是:第一第一第一第一:在在在在a0a0到到到到aN-1aN-1的范围内的范围内的范围内的范围内,依次比较两个相邻元素的值依次比较两个相邻元素的值依次比较两个相邻元素的值依次比较两个相邻元

3、素的值,若若若若aJaJ+1,aJaJ+1,则交换则交换则交换则交换aJaJ与与与与aJ+1,JaJ+1,J的值取的值取的值取的值取0,1,2,N-2;0,1,2,N-2;经过经过经过经过这样一趟冒泡这样一趟冒泡这样一趟冒泡这样一趟冒泡,就把这就把这就把这就把这N N个数中最大的数放到个数中最大的数放到个数中最大的数放到个数中最大的数放到aN-1aN-1中中中中.看图示看图示看图示看图示 例例1:用冒泡排序法对用冒泡排序法对8个整数个整数6,8,5,4,6,9,3,2进行从小到进行从小到大排序大排序.冒泡法原理冒泡法原理 第二第二:再对再对a0到到aN-2的范围内再进行一趟冒泡的范围内再进行一

4、趟冒泡,又将该范又将该范围内的最大值换到了围内的最大值换到了aN-2中中.看图示二看图示二看图示二看图示二SwapSwap变量作用变量作用变量作用变量作用看图示三看图示三看图示三看图示三 第四第四:如果在某趟冒泡过程中没有交换相邻的值如果在某趟冒泡过程中没有交换相邻的值,则说明排序则说明排序已完成已完成,可以提前结束处理可以提前结束处理.第三第三:依次进行下去依次进行下去,最多只要进行最多只要进行N-1趟冒泡趟冒泡,就可完成排序就可完成排序.看流程看流程看流程看流程冒泡法排序冒泡法排序现假设有现假设有现假设有现假设有8 8 8 8个随机数已经在数组中，开始排序个随机数已经在数组中，开始排序个随

5、机数已经在数组中，开始排序个随机数已经在数组中，开始排序初始状态：初始状态：初始状态：初始状态：数组数组数组数组a a a a a0 a1 a2 a3 a4 a5 a6 a7a0 a1 a2 a3 a4 a5 a6 a76 6 6 68 8 8 85 5 5 54 4 4 46 6 6 69 9 9 93 3 3 32 2 2 2 第一趟排序：第一趟排序：第一趟排序：第一趟排序：两两相邻比较：两两相邻比较：两两相邻比较：两两相邻比较：总结总结总结总结回到思路一回到思路一回到思路一回到思路一8 85 58 84 49 93 38 86 69 92 2第一趟最后结果：第一趟最后结果：第一趟最后结果

6、：第一趟最后结果：9 9第二趟冒泡排序开始：第二趟冒泡排序开始：第二趟冒泡排序开始：第二趟冒泡排序开始：此时的待排序元素此时的待排序元素此时的待排序元素此时的待排序元素 a0 a1 a2 a3 a4 a5 a6a0 a1 a2 a3 a4 a5 a6 a7a7 冒泡法排序冒泡法排序6 6 6 65 5 5 54 4 4 46 6 6 68 8 8 83 3 3 32 2 2 29 9 9 95 5 5 54 4 4 46 6 6 66 6 6 63 3 3 32 2 2 28 8 8 89 9 9 94 4 4 45 5 5 56 6 6 63 3 3 32 2 2 26 6 6 68 8 8

7、 89 9 9 9同样对待排序元素两两比较后结果为：同样对待排序元素两两比较后结果为：同样对待排序元素两两比较后结果为：同样对待排序元素两两比较后结果为：这是第三趟冒泡的待排序元素这是第三趟冒泡的待排序元素这是第三趟冒泡的待排序元素这是第三趟冒泡的待排序元素接着第三趟冒泡接着第三趟冒泡接着第三趟冒泡接着第三趟冒泡排序结果为：排序结果为：排序结果为：排序结果为：回到思路二回到思路二回到思路二回到思路二冒泡法排序冒泡法排序同样第四趟结果为：同样第四趟结果为：同样第四趟结果为：同样第四趟结果为：2 2 2 23 3 3 34 4 4 45 5 5 56 6 6 66 6 6 68 8 8 89 9

8、9 94 4 4 45 5 5 53 3 3 32 2 2 26 6 6 66 6 6 68 8 8 89 9 9 93 3 3 32 2 2 24 4 4 45 5 5 56 6 6 66 6 6 68 8 8 89 9 9 94 4 4 43 3 3 32 2 2 25 5 5 56 6 6 66 6 6 68 8 8 89 9 9 9第六趟结果为：第六趟结果为：第六趟结果为：第六趟结果为：第七趟结果（最终）为：第七趟结果（最终）为：第七趟结果（最终）为：第七趟结果（最终）为：第五趟结果为：第五趟结果为：第五趟结果为：第五趟结果为：回到思路二回到思路二回到思路二回到思路二看流程看流程看流程

9、看流程冒泡法排序流程图冒泡法排序流程图程序整体流程：程序整体流程：程序整体流程：程序整体流程：开始开始开始开始结束结束结束结束输入数据输入数据输入数据输入数据输出数据输出数据输出数据输出数据冒泡排序冒泡排序细化输入数据流程：细化输入数据流程：细化输入数据流程：细化输入数据流程：i=0i=0i8i8MOVX A,DPTRMOVX A,DPTRi+i+N NY Y细化输出数据流程：细化输出数据流程：细化输出数据流程：细化输出数据流程：i=0i=0i8i8MOVX DPTR,AMOVX DPTR,Ai+i+N NY Y执行第执行第i趟趟冒泡排序冒泡排序冒泡法排序流程图冒泡法排序流程图i+i+i8-1

10、i8-1i=0i=0Y YN N写程序写程序写程序写程序j=0j=0j8-i-1jaj+1ajaj+1交换交换交换交换ajaj与与与与aj+1aj+1的值的值的值的值Y YN N冒泡法排序流程图冒泡法排序流程图ajaj+1ajaj+1 swap=1;swap=1;交换交换交换交换ajaj与与与与 aj+1 aj+1的值的值的值的值Y YN Ni+;i+;i8-1i8-1i=0i=0Y YN Nj8-i-1j8-i-1N N Y Yj+j+swap=0swap=0j=0j=0加加加加入入入入SwapSwap变变变变量量量量的的的的流流流流程程程程图图图图程程程程 序序序序!(swap)!(swa

11、p)breakbreakN NY Y冒泡法程序冒泡法程序main()main()main()main()int i,j,a8,temp,swap;int i,j,a8,temp,swap;int i,j,a8,temp,swap;int i,j,a8,temp,swap;clrscr();clrscr();clrscr();clrscr();for(i=0;i8;i+)for(i=0;i8;i+)for(i=0;i8;i+)for(i=0;i8;i+)scanf(%d,&ai);scanf(%d,&ai);scanf(%d,&ai);scanf(%d,&ai);for(i=0;i8;i+)fo

12、r(i=0;i aj+1)if(aj aj+1)temp=aj;temp=aj;aj=aj+1;aj=aj+1;aj+1=temp;aj+1=temp;for(j=0;jfor(j=0;j8-i-18-i-1;j+);j+)回到第四点回到第四点回到第四点回到第四点上一页上一页上一页上一页比较比较比较比较for(i=0;i8-1;i+)for(i=0;i8-1;i+)冒泡法冒泡法swap swap 变量的作用变量的作用 如果在某趟冒泡过程中没有交换相邻的值如果在某趟冒泡过程中没有交换相邻的值如果在某趟冒泡过程中没有交换相邻的值如果在某趟冒泡过程中没有交换相邻的值,则则则则说明排序说明排序说明排序

13、说明排序已完成已完成已完成已完成,可以提前结束处理可以提前结束处理可以提前结束处理可以提前结束处理.比如：为原始数列：比如：为原始数列：比如：为原始数列：比如：为原始数列：8 8、1515、2727、9696、3232、6565、7878、7979 这个序列用冒泡法排序，这个序列用冒泡法排序，这个序列用冒泡法排序，这个序列用冒泡法排序，一趟之后就得到升序结果一趟之后就得到升序结果一趟之后就得到升序结果一趟之后就得到升序结果，而之后的六趟都可以不要进行。而之后的六趟都可以不要进行。而之后的六趟都可以不要进行。而之后的六趟都可以不要进行。所以，所以，所以，所以，swapswap变量变量变量变量就是

14、就是就是就是用来标识如果某趟排序之后已经用来标识如果某趟排序之后已经用来标识如果某趟排序之后已经用来标识如果某趟排序之后已经得到最终结果得到最终结果得到最终结果得到最终结果，则多余的次数就无须进行。，则多余的次数就无须进行。，则多余的次数就无须进行。，则多余的次数就无须进行。回到流程图回到流程图回到流程图回到流程图冒泡法与选择法的比较冒泡法与选择法的比较用选择排序法对键盘输入的用选择排序法对键盘输入的用选择排序法对键盘输入的用选择排序法对键盘输入的N N N N个数从小到大进行排序个数从小到大进行排序个数从小到大进行排序个数从小到大进行排序.基本思想基本思想基本思想基本思想:假设有假设有假设有

15、假设有N N个数据放在数组个数据放在数组个数据放在数组个数据放在数组a a中中中中,现要把这现要把这现要把这现要把这N N个数从小到大排序个数从小到大排序个数从小到大排序个数从小到大排序.首先首先首先首先:在在在在a0a0到到到到aN-1aN-1的范围内的范围内的范围内的范围内,选出最小值与选出最小值与选出最小值与选出最小值与a0a0交换交换交换交换;然后然后然后然后:在在在在a1a1到到到到aN-1aN-1范围内范围内范围内范围内,选出最小值与选出最小值与选出最小值与选出最小值与a1a1交换交换交换交换;接着是接着是接着是接着是a2a2到到到到aN-1aN-1的范围，这样依次进行下去的范围，

16、这样依次进行下去的范围，这样依次进行下去的范围，这样依次进行下去,进行进行进行进行N-1N-1次选次选次选次选择后就可完成排序择后就可完成排序择后就可完成排序择后就可完成排序.即第即第即第即第i i趟排序的待排序范围是趟排序的待排序范围是趟排序的待排序范围是趟排序的待排序范围是aiaN-1aiaN-1的元的元的元的元素，要从中选出值最小的元素并与素，要从中选出值最小的元素并与素，要从中选出值最小的元素并与素，要从中选出值最小的元素并与aiai交换位置。交换位置。交换位置。交换位置。冒泡法与选择法的比较冒泡法与选择法的比较 a0 a1 a2 a3 a4 a5 a6 a7 a0 a1 a2 a3

17、a4 a5 a6 a7数组数组数组数组a a a a6 6 6 68 8 8 85 5 5 54 4 4 46 6 6 69 9 9 93 3 3 32 2 2 2KKiKKK2 26 6 每趟选择排序是找到待排序序列中最小每趟选择排序是找到待排序序列中最小的元素，把它交换到待排序的最前的位置。的元素，把它交换到待排序的最前的位置。所以，一趟只有一次交换。所以，一趟只有一次交换。回到冒泡图示回到冒泡图示回到冒泡图示回到冒泡图示iKK3 38 84 45 5 5 56 66 69 98 8总总 结结本次课主要内容：本次课主要内容：本次课主要内容：本次课主要内容：1.1.1.1.冒泡法基本思想，通

18、过冒泡法基本思想，通过冒泡法基本思想，通过冒泡法基本思想，通过n-1n-1n-1n-1趟排序把趟排序把趟排序把趟排序把n n n n个待排序数个待排序数个待排序数个待排序数大的元素象石头一样往下沉（放在最后），小的元素大的元素象石头一样往下沉（放在最后），小的元素大的元素象石头一样往下沉（放在最后），小的元素大的元素象石头一样往下沉（放在最后），小的元素象气泡一样往上浮。象气泡一样往上浮。象气泡一样往上浮。象气泡一样往上浮。2.2.2.2.冒泡法的流程图冒泡法的流程图冒泡法的流程图冒泡法的流程图 3.3.3.3.冒泡法程序冒泡法程序冒泡法程序冒泡法程序 4.4.4.4.冒泡法中冒泡法中冒泡法中冒泡法中swapswapswapswap变量的作用变量的作用变量的作用变量的作用 5.5.5.5.简述了选择法排序，要求回去预习选择法排序。简述了选择法排序，要求回去预习选择法排序。简述了选择法排序，要求回去预习选择法排序。简述了选择法排序，要求回去预习选择法排序。