一.排序方法
- 将被排列的数组data[0...n]垂直排列,每个元素data[i]看作是一个气泡,气泡的重量就是data[i]的值。
- 从最下面一个气泡data[n]开始扫描,比较其与上一个气泡data[n-1]的重量,data[n] < data[n-1]则交换;然后比较data[n-1]与data[n-1-1]...一轮下来,最轻的气泡跑到了最上面data[0]的位置。
- 重复2过程,让第二轻的气泡跑到data[1]的位置;再次重复...
二.动画演示
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/maopaopaixu.htm
三.Java代码
- public static int[] bubbleSort(int[] data) {
- int temp = 0;
- for(int i=0; i < data.length -1; i++) { //每一轮
- boolean exchange = false; //每一轮设置一个是否有元素交换的标志
- int j = data.length -1;
- for(; j > i; j--) {
- if(data[j] < data[j-1]) { //元素和上一个元素比较
- temp = data[j];
- data[j] = data[j-1];
- data[j-1] = temp;
- exchange = true; //有元素交换
- }
- }
- if(!exchange) { //如果一轮下来,没有元素交换,说明data已经是排好序了,无需进行下一轮
- break;
- }
- }
- return data;
- }
四.时间复杂度和稳定性
- 最好时间复杂度
- 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值。
- Cmin=n-1=O(n)
- Mmin=0
- 冒泡排序最好的时间复杂度为O(n)
- 最坏时间复杂度
- 若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值。
- Cmax=n(n-1)/2=O(n2)
- Mmax=3n(n-1)/2=O(n2)
- 冒泡排序的最坏时间复杂度为O(n2)
- 平均时间复杂度
- O(n2)
- 冒泡排序是就地排序,且它是稳定的。
五.算法优化
- 设置exchange标志。如果不设置,Cmin=n(n-1)/2=O(n2)
相关推荐
51单片机控制的循迹避障小车,支持红外遥控,可以实现前进后退左右和循迹切换
智能小车的相关功能例程,并且有程序的注释,
为了提高资源采出率,确保矿井安全高效生产,实现厚煤层一次采全高,平煤股份决定在十二矿上马一套大型综采设备。该套设备采用ZY6400-23.5/45型液压支架,最大采高达4.5 m。由于十二矿井下主要巷道断面较小,支架必须解体...
ZY3-01星SC产品命名规范20160217.pdf
ZY-TP21便捷式打印机驱动是一款嵌入式微型打印机,这款打印机体积小,重量轻,噪音低,易集成,操作简单,可靠性强,这里介绍的正是针对这款打印机的驱动,ZY-TP21便捷式打印机驱动,有需要的朋友们快来下载吧。...
ZY-Player-Setup-2.6.4.exe
RF-SJ-ZY-04-F03 结构专业图纸审查标准及要点.zip
循迹小车的单片机程序。仅供参考大家互相学习,共同进步本次上传日志本次上传日志本次上传日志本次上传日志要求上传您自己觉得好的资料本次上传日志
不用换找资源,本身自带资源搜索的播放器
RF-SJ-ZY-04-F03 结构专业图纸审查标准及要点(1).zip
ZY-Player-Setup-2.6.1.exe
RF-GC-ZY-04-F03 管道打压验收标准.zip
ZY-Player清醒脱俗的一款播放器,无广告,速度快。
zy-player PC端
RF-GC-ZY-04-F01 房屋验收记录单.zip
程序设计语言ZY1906-大作业.7z
ZY5600-16-34型液压支架掩护梁有限元分析及其优化设计,蒲志新,邓全刚,以ZY5600-16-34型液压支架为研究对象,利用Pro/E软件对其液压支架进行三维建模,然后利用ANSYS软件对液压支架的强度进行有限元分析,并�
RF-SJ-ZY-04-F08 采暖通风设计图纸审查标准及要点(1).zip