从简单开始，冒泡排序的思路、实现、优化
⼀、什么是排序算法？
顾名思义，排序算法就是将⼀组数据按照某种⽐较⽅法进⾏排序的算法，是⼀种算法。
例如数据是⼀组数字，通过排序算法可以将这组数字由⼩到⼤或由⼤到⼩排列。
例如⼀组数字：5，8，9，6，3，2，4，1，7。
输⼊排序算法后得到：1，2，3，4，5，6，7，8，9。
ps：在排序算法中只使⽤运算符和⾃⼰实现的⽅法，不然是犯规的哦~
基础的排序算法：冒泡排序，选择排序，插⼊排序等。
进阶的排序算法还有：希尔排序，归并排序，桶排序，计数排序等等。
附：排序算法的稳定性，指的是在执⾏排序算法执⾏之后，⽐较后值相等的两个数据相对位置不变。⽐如班级中的⼈按照⾝⾼进⾏排队，张三和李四⼀样⾼，排队之前张三排在李四前⾯，在⽼师排好队后，张三排在李四后⾯了，那么⽼师排队的⽅法就是⼀个不稳定的排序算法。有的同学可能会问了，排序算
法为什么要保证稳定性呢？那么我们回到刚才的排队问题上来，如果在按⾝⾼排队之前，同学已经按照是否是近视以及近视的程度排了⼀遍队了，那么保证这个队伍的顺序就很有必要了。在编程语⾔中多数情况都是对“对象”（如果不认识请⾃⾏百度）进⾏排序，因为“对象”会有很多属性，很可能根据多个属性进⾏多次排序，这时排序算法的稳定性就显得很重要了（⼏乎所有编程语⾔提供的排序功能使⽤的都是稳定的排序算法）。
学习排序算法之前需要了解的事情：⼀门编程语⾔的基本分⽀和循环语句，各种运算符的使⽤。数组的数据结构和基本使⽤。
⼆、冒泡排序设计思路
冒泡排序是⽐较基本的排序算法，排序算法中⼜是算法中⽐较基础的算法。所以⼊门算法⾸先要掌握排序算法，尤其要掌握冒泡排序。
顾名思义，冒泡排序就是将数据⽐作泡泡，更⼤的数据往上冒。（以下都以数字组成的数组为案例）。例：8，5，9，6。
冒泡排序代码c语言冒泡排序的基本数据：平均时间复杂度：O（n²），最慢时间复杂度：O（n²），最快时间复杂度：O（n²）------优化后可为
O（n），稳定性：稳定。
这⾥先提⼀下指针：很多新⼿没办法理解指针表达含义，不同于c语⾔中的指针，这⾥的指针可以理解为正在操作的数据，在许多算法的实现中，指针都是重要切难以理解部分。在下⾯的代码实现中，我也会重点指出，帮助⼤家理解指针，快速⼊门算法。
mysql查询结果取交集
1. ⾸先从数组第0位开始遍历这个数组。既将指针指向第0位。
8596
2. 如果第0位⽐第1位⼤，则交换这两个数的位置，否则两个数位置不变，并将指针移动到下⼀位既第1位。
5896
3. 继续从指针的位置重复上⾯的过程，直到指针指向数组最后⼀位。
5896
5896
5869
4. 这时指针所在的位置就是当前数组中最⼤的数字。或者可以说指针左⾯的数字都⽐它⼩。
5869
5. 对指针左⾯剩余数据再次执⾏上⾯的过程。                                                                                                          指针从0开
始：
5869
与下⼀位⽐较，不⼤于，指针指向下⼀位：
5869
与下⼀位⽐较，⼤于，交换位置，指针指向下⼀位：
floatingmaterial在线看5689
剩余数据已经全部⽐较完成：
frameborder什么意思5689
继续对左侧剩余数据执⾏，指针指向0：
5689
与下⼀位⽐较，不⼤于，指针指向下⼀位：
5689
剩余数据⽐较完成：
5689
6. 剩下最后⼀个数据时，结束算法：
5689
这时我们就得到了⼀个有序的数组：5，6，8，9。
三、冒泡排序代码实现
⾸先实现单次冒泡的过程，即把数组中最⼤的数移动到数组末尾的位置。
int[] arr = new int[]{8,5,9,6};//定义数组
int i = 0;//这个就是指针，注意指针每次的变化
for(;i < arr.length -1;i++){//注意需要到数组倒数第⼆位，因为下⾯是取后⼀位⽐较，否则会越界
//交换两个变量的值，最基本的...
if(arr[i] > arr[i + 1]){
int num = arr[i + 1];//先把后⾯的值存到临时变量⾥
arr[i + 1] = arr[i];//再把前⾯的值赋给后⾯
arr[i] = num;//最后把临时变量中存的后⾯的值赋给前⾯
}
}
/
/或者也可以⽤
//      while (i < arr.length-1){
//          i++;
//      }
//都⼀样
结果打印出来：5，8，6，9。
没问题，和想象的⼀样。
现在我们要做的就是让程序每次在已经冒泡的数据之前停下，也就是停⽌的位置每次向前⼀位。先打印出需要停⽌的下标。
for(int j = arr.length; j > 1 ; j--){//为什么是j > 1呢，因为到下标到⼀的时候就证明程序需要在指针下标⼩于⼀的时候停⽌，也就是只剩下⼀位数字了
System.out.print(j-1);//这⾥减⼀是因为我们想要获取下标，下标是从0开始的⽽长度是从1开始的，挺
反⼈类的，不过代码敲多了习惯了就好
}
打印出结果321，没问题，第⼀次指针⼩于下标三，第⼆次⼩于下标⼆，第三次⼩于下标1，最后程序结束。
现在我们要组合起来，让我们的单次冒泡多次执⾏，并且在规定的位置结束
for(int j = arr.length; j > 1 ; j--){
for(int i = 0;i < j -1;i++){//每次指针归零，并且在j-1处停⽌
if(arr[i] > arr[i + 1]){
int num = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = num;//
}
}
}
打印数据:5,6,8,9。
没问题，⼤功告成，⼀个基本的冒泡排序就实现了。
注意在⾃⼰实现的过程中⼀定要多准备⼏组数据反复测试，以免出现意想不到bug。
四、冒泡排序的优化
通过上⾯的⽂章可以得到冒泡排序的设计思路和实现过程，不过真正理解的同学都会有⼀个疑问，这个算法⽆论如何时间复杂度都是
O（n²）啊，为什么会有复杂度O（n）的情况呢？
想要优化⼀个算法需要对算法这门学科有深刻的研究，那么对于初学者来说，不如从结论下⼿，⽤结论反向推导过程，更能够帮助我们开拓思维。
这⾥我们已经得到了优化后的时间复杂度为O（n），也就是说只对数组进⾏了⼀次遍历，对于冒泡排
序来说，也就是我们如果能够在第⼀次冒泡结束以后，就能够判断整个数组是有序的，那么整个过程就只进⾏了⼀次遍历。
那么如何判断⼀次冒泡过程结束以后，数组是有序的呢，不难理解，如果这次冒泡的过程中，⼀次数据交换都没有发⽣，那么次冒泡结束以后，数组必定是排好序的。所以，我们只需要在每次冒泡过程开始时增加⼀个标识来判断是否有数据交换产⽣，并在数据交换产⽣后更改这个值，就可以判断这次冒泡过程有没有数据交换了，如果标识没有修改过，就证明这次冒泡结束后，数组已经是有序的了，不需要在进⾏后⾯的冒泡了。
代码实现：
int[] arr = new int[]{1,2,3,4,5,6,7,8,9};//定义⼀个⽐较极端的情况
int count = 0;
for(int j = arr.length; j > 1 ; j--){
boolean flag = false;//标识符
for(int i = 0;i < j -1;i++){//每次指针归零，并且在j-1处停⽌
if(arr[i] > arr[i + 1]){
c语言程序在哪下载int num = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = num;
flag = true;//如果交换产⽣则修改标识符
}
count++;//计算执⾏次数
}
if(flag == false){//如果没有交换产⽣则结束循环
break;
}
}
网络编程用什么软件执⾏后得到结论为，优化前算法执⾏36次，优化后执⾏8次，与预期结果⼀致。⾄此冒泡排序的思路、实现、优化 就全部了解了。
第⼀次写博客，希望⼤家多多指教~

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。