冒泡排序是程序猿的必备技能，虽说API里面有这个排序方法了，但是遇到大型数据的话，运行起来还是很慢，占用内存，现在我们可以将它优化一下便于使用。
- 未优化的冒泡排序
//未优化的冒泡排序
public static void getSort1(int[] arr){
//提前将长度赋值，降低循环内赋值操作次数
int temp = arr.length;
//遍历数组
for(int i=0;i<temp;i++){
//内循环交换元素
for(int j=0;j<temp-i-1;j++){
if(arr[j]>arr[j+1]){
swop(arr,j);
}
}
}
}
- 外层的优化
根据冒泡排序的概念，手写五个数的冒泡排序流程之后，我们可以发现当进行首次排序之后，最后一个数已经固定了，那么到第三次排序的时候，其实就可以省掉对最后两个数的比较次数，达到节约资源的效果。
//优化外层循环的冒泡，仅适用于连片有序但整体无序的数据，不适用于前面大部分无序，后面小部分有序的数据
public static void getSort2(int[] arr){
//提前将长度赋值，降低循环内赋值操作次数
int temp = arr.length-1;
//遍历数组
for(int i=0;i<temp;i++){
//设置一个标志flag，如果此数据已排好序则flag=true，否则为false
boolean flag = false;
//内循环交换元素，已排好序则更改状态为true
for(int j=0;j<temp-i;j++){
if(arr[j]>arr[j+1]){
swop(arr,j);
//数据交换完毕，更改flag状态
flag = true;
}
}
//flag是记录数据交换的状态，若为false，则表明不用进行剩下的排序了
if(flag == false){
break;
}
}
}
3.内层优化
内层的优化是建立在外层优化的基础上，在外层优化之后，我们发现运行时间节约了一半，但是还有可以优化的空间，这个空间就是当外层优化的程序运行到某个位置时，其实此元素后面有一小半已经是排好序了，此元素的下一个元素根本不用去比较到该元素之后的位置，只用将该元素最后一次交换位置的索引值，当做下一个元素比较的次数就可以了，又节省了三分之一的时间。
//优化内层循环，将每次比较的最后一次的下标记录下来，作为下一次数据比较的次数
public static void getSort3(int[] arr){
//定义一个变量储存每次需要循环的次数，使其成为下一个元素循环的次数
int temp = arr.length-1;
//定义一个变量储存比较次数
int flag;
//遍历数组
while(temp>0){
//初始化循环次数
flag = temp;
temp = 0;
for(int i=0;i<flag;i++){
if(arr[i]>arr[i+1]){
swop(arr,i);
temp = i;
}
}
}
}
被单独写出来的元素交换
//数组元素交换
public static void swop(int[] arr,int i){
int t = arr[i];
arr[i] = arr[i+1];
arr[i+1] = t;
}
- 鸡尾酒排序
鸡尾酒排序又被称为双向冒泡排序，实现起来挺简单的，在资源节约上比原版本好一些，但是还是比不上外层优化甚至内层优化的冒泡排序。
//双向冒泡排序
public static void getSort4(int[] arr){
//从小到大
int temp = arr.length;
for(int i=0;i<temp/2;i++){
for(int j=i;j<temp-i-1;j++){
if(arr[i]>arr[i+1]){
swop(arr,i);
}
}
//从大到小
for(int j=temp-i-1;j>i;j--){
if(arr[j]<arr[j-1]){
int t = arr[j];
arr[j] = arr[j-1];
arr[j-1] = t;
}
}
}
}
若是将外层优化甚至内层优化写进鸡尾酒排序中，排序占用时间将变得不稳定而且耗时也就比原版本好一点点，我这里估计的原因是内存占用过多，空间占用太多，JVM运行变慢，达不到空间换时间的效果。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/75269.html
