冒泡法排序原理教学资料.ppt
冒泡法排序原理经典算法介绍：经典算法介绍：排序问题是程序设计中的典型问题之一，它有很广泛排序问题是程序设计中的典型问题之一，它有很广泛的应用，比如给你一组学生成绩，要你输出前的应用，比如给你一组学生成绩，要你输出前2 0 名的成绩。名的成绩。这时你就要用到排序。再比如要问你中国的这时你就要用到排序。再比如要问你中国的GDP排世界第排世界第几，你要先把各国几，你要先把各国GDP排个序，才知道中国在第几。排个序，才知道中国在第几。所谓排序就是将数组中的各元素的值按从小到大的顺所谓排序就是将数组中的各元素的值按从小到大的顺序或按从大到小的顺序重新排列。序或按从大到小的顺序重新排列。排序过程一般都要进行元素值的比较和元素值的交换。排序过程一般都要进行元素值的比较和元素值的交换。冒泡法排序冒泡法排序第二趟冒泡排序开始：第二趟冒泡排序开始：第二趟冒泡排序开始：第二趟冒泡排序开始：此时的待排序元素此时的待排序元素此时的待排序元素此时的待排序元素 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 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 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第六趟结果为：第六趟结果为：第六趟结果为：第六趟结果为：第七趟结果（最终）为：第七趟结果（最终）为：第七趟结果（最终）为：第七趟结果（最终）为：第五趟结果为：第五趟结果为：第五趟结果为：第五趟结果为：回到思路二回到思路二回到思路二回到思路二看流程看流程看流程看流程冒泡法排序流程图冒泡法排序流程图程序整体流程：程序整体流程：程序整体流程：程序整体流程：开始开始开始开始结束结束结束结束输入数据输入数据输入数据输入数据输出数据输出数据输出数据输出数据冒泡排序冒泡排序细化输入数据流程：细化输入数据流程：细化输入数据流程：细化输入数据流程：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-1i8-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)!(swap)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+)for(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 变量的作用变量的作用 如果在某趟冒泡过程中没有交换相邻的值如果在某趟冒泡过程中没有交换相邻的值如果在某趟冒泡过程中没有交换相邻的值如果在某趟冒泡过程中没有交换相邻的值,则则则则说明排序说明排序说明排序说明排序已完成已完成已完成已完成,可以提前结束处理可以提前结束处理可以提前结束处理可以提前结束处理.比如：为原始数列：比如：为原始数列：比如：为原始数列：比如：为原始数列：8 8、1515、2727、9696、3232、6565、7878、7979 这个序列用冒泡法排序，这个序列用冒泡法排序，这个序列用冒泡法排序，这个序列用冒泡法排序，一趟之后就得到升序结果一趟之后就得到升序结果一趟之后就得到升序结果一趟之后就得到升序结果，而之后的六趟都可以不要进行。而之后的六趟都可以不要进行。而之后的六趟都可以不要进行。而之后的六趟都可以不要进行。所以，所以，所以，所以，swapswap变量变量变量变量就是就是就是就是用来标识如果某趟排序之后已经用来标识如果某趟排序之后已经用来标识如果某趟排序之后已经用来标识如果某趟排序之后已经得到最终结果得到最终结果得到最终结果得到最终结果，则多余的次数就无须进行。，则多余的次数就无须进行。，则多余的次数就无须进行。，则多余的次数就无须进行。回到流程图回到流程图回到流程图回到流程图冒泡法与选择法的比较冒泡法与选择法的比较用选择排序法对键盘输入的用选择排序法对键盘输入的用选择排序法对键盘输入的用选择排序法对键盘输入的N N N N个数从小到大进行排序个数从小到大进行排序个数从小到大进行排序个数从小到大进行排序.基本思想基本思想基本思想基本思想:假设有假设有假设有假设有N N个数据放在数组个数据放在数组个数据放在数组个数据放在数组a a中中中中,现要把这现要把这现要把这现要把这N N个数从小到大排序个数从小到大排序个数从小到大排序个数从小到大排序.首先首先首先首先:在在在在a0a0到到到到aN-1aN-1的范围内的范围内的范围内的范围内,选出最小值与选出最小值与选出最小值与选出最小值与a0a0交换交换交换交换;然后然后然后然后:在在在在a1a1到到到到aN-1aN-1范围内范围内范围内范围内,选出最小值与选出最小值与选出最小值与选出最小值与a1a1交换交换交换交换;接着是接着是接着是接着是a2a2到到到到aN-1aN-1的范围，这样依次进行下去的范围，这样依次进行下去的范围，这样依次进行下去的范围，这样依次进行下去,进行进行进行进行N-1N-1次选次选次选次选择后就可完成排序择后就可完成排序择后就可完成排序择后就可完成排序.即第即第即第即第i i趟排序的待排序范围是趟排序的待排序范围是趟排序的待排序范围是趟排序的待排序范围是aiaN-1aiaN-1的元的元的元的元素，要从中选出值最小的元素并与素，要从中选出值最小的元素并与素，要从中选出值最小的元素并与素，要从中选出值最小的元素并与aiai交换位置。交换位置。交换位置。交换位置。冒泡法与选择法的比较冒泡法与选择法的比较 a0 a1 a2 a3 a4 a5 a6 a7 a0 a1 a2 a3 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.冒泡法基本思想，通过冒泡法基本思想，通过冒泡法基本思想，通过冒泡法基本思想，通过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.简述了选择法排序，要求回去预习选择法排序。简述了选择法排序，要求回去预习选择法排序。简述了选择法排序，要求回去预习选择法排序。简述了选择法排序，要求回去预习选择法排序。结束语结束语谢谢大家聆听！谢谢大家聆听！16
