高中：冒泡排序算法程序实现—推导

冒泡排序算法程序实现一推导©班级学号姓名©列表d=

[27363218]升序排序冒泡排序程序实现推导过程如下

一、由内而外的推导

1.第1遍加工程序实现推导（第2遍、第3遍加工推导方法同）算法描述不使用循环的程序实现:前数j-1和后数j的变化呈现出有规律的递减，可以推导出“使用循环的程序”实现:forjinrange（目同-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]

2.3遍加工合成双循环

二、由外而内的推导

1.每遍加工分析将上面表格算法描述描写为伪代码:foriinrangel4:#将的最小值放到第卜d

[3]中的最小值放到代码推导

①将d[a]~d[b]中的最小值以冒泡的方式放到d[a]中的程序实现（a〈b）算法描述:程序实现forjinrange®-1:d[j]d[j-l]=d[j-l]d[j]

②中的最小值放到代码用上面代码进行代换forjinrangeM-1:d[j]d[j-l]=d[j-l]d[j]foriinrangelJ4:forjinrange|H叵-1d[j]d[j-l]=d[j-l]d[j]注由外而内的推导方法，可以认为内层循环的代码是一个函数函数，该“函数”在循环变量i取不同值的情况下被分别调用

三、列表d（n个数据）升序排序冒泡排序程序由内而外的推导（每遍加工的推导参考前面）

四、列表d（n个数据）升序排序冒泡排序程序由外而内的推导

1.每遍加工分析将上面表格算法描述描写为伪代码foriinrangeln:#将d[i-lkd[n-l]的最小值放到第中的最小值放到代码推导参考列表4个元素由外而内冒泡的二2

①forjinrange瓦囿-1ifd[j]d[j-l]:d[j]d[j-l]=d[j]可得forjinrangel|-1:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]

3.将1中的“#将的最小值放到第用2代码代换foriinrangelJn:forjinrangepTl]-1:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]比较次数后数前数算法描述d[j]d[j-l]d[j]比小则交换d[j]、d[j-l]1d

[3]d

[2]d

[3]比d

[2]小则交换d

[3]、d

[2]2d

[2]d[l]d

[2]比d[l]小则交换d

[2]、d[l]3d[l]d

[0]d[l]比d

[0]小则交换d[l]、d

[0]合成前（框内数字规律变化）合成后（规律变化数字转化为i）第1遍forjinrange（3j瓦-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]foriinrange（比目）forjinrange（3i-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]上面代码可以转化为如下的代码，其中i的含义表示第？遍加工foriinrange（国，@）:forjinrange（3-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]第2遍forjinrange（3j国，-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]第3遍forjinrange（3^目-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]加工遍数操作1将d

[0]到d

[3]中的最小值放到第d

[0]2将d[l]到d

[3]中的最小值放到第d[l]3将d

[2]到d

[3]中的最小值放到第d

[2]比较次数后数前数算法描述d[j]d[j-l]d[j]比小则交换d[j]、d[j-l]1d[b]d[b-l]d[b]比d[b-l]小则交换d[b]、d[b-l]2d[b-l]d[b-2]d[b-1]比d[b-2]小则交换d[b-l]、d[b-2]••••••••••••d[a+2]d[a+l]d[a+2]比d[a+l]小则交换d[a+2]d[a+l]d[a+l]d[a]d[a+1]比d[a]小则交换d[a+l]、d[a]合成前合成后第1遍forjinrange（n-l瓦-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]第2遍forjinrange（n-l国，-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]foriinrange（瓦|n-l|）:forjinrange（n-lJi-1）:ifd[j]d[j-l]:第3遍forjinrange（n-l目，-1）ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]d[j]d[j-l]=d[j-l]d[j]上面代码可以转化为如下的代码，其中i的含义表示第？遍加工foriinrange（国，[n]）:第n-2遍forjinrange（n-l|n-3|-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]forjinrange（n-l|i-l|-1）:ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]第n-1遍forjinrange（n-l垣-1）ifd[j]d[j-l]:d[j]d[j-l]=d[j-l]d[j]加工遍数操作1将d

[0]到d[n-l]中的最小值放到第d

[0]2将d[l]到d[n-l]中的最小值放到第d[l]3将d

[2]到d[n-l]中的最小值放到第d

[2]n-1将d[n-2]到d[n-l]中的最小值放到d[n-2]。