冒泡排序真的性能差吗
一个被人遗忘的排序算法-梳排序(combsort)
本质： 分组的冒泡排序。
先来看实现吧，基于冒泡排序和梳排序的一个直接对比
import java.util.Arrays;
public class CombSort {//梳排序 基于冒泡排序的优化：分组冒泡排序
private static final CombSort opt = new CombSort();
public static void main(String[] args) {
int[] arr = {2,1,2,5,4,3,3,6,7,8,6,5,4,3,5,2,1,2,5,4,3,3,6,7,8,6,5,4,3,5};
System.out.println("原数组："+Arrays.toString(arr));
opt.bubbleSort(arr);
System.out.println(Arrays.toString(arr));
int[] arr1 = {2,1,2,5,4,3,3,6,7,8,6,5,4,3,5,2,1,2,5,4,3,3,6,7,8,6,5,4,3,5};
opt.combSort(arr1);
System.out.println(Arrays.toString(arr1));
}
//冒泡排序
public void bubbleSort(int[] arr){//从小到大
int count = 0;
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){//时间复杂度O(n^2) （n-1）+（n-2）+...+2+1 = n(n-1)/2 等于n平方量阶
if(arr[j]>arr[j+1]){
arr[j] = arr[j] ^ arr[j+1];
arr[j+1] = arr[j] ^ arr[j+1];
arr[j] = arr[j] ^ arr[j+1];
count++;
}
}
}
System.out.println("bubbleSort交换次数："+count);
}
//梳排序
/*
* 分组冒泡 类比希尔排序：希尔排序基于插入排序实现， 梳排序基于冒泡实现
* 每次比较 i 和 i+j 以j跨步作冒泡排序
* j 数组长度每次除以1.3向下取整
* 同时设置一个标志位flag初始为true，每次进行内层判断时初始化false，只要内层进行了交换
* 说明当前的元素还没有排序好，所以设置flag为true继续循环
* */
public void combSort(int[] arr){
int step = arr.length;
int count = 0;
int count2 = 0;
boolean flag = true;
while (flag || step > 1){//step = 1 的时候 会做一次冒泡 只有在flagtrue时候才会执行
int i=0;
flag = false;
step = (step/1.3)>1?(int)(step/1.3):1;
count2++;
while(i+step<arr.length){
if(arr[i]>arr[i+step]){
arr[i] = arr[i] ^ arr[i+step];
arr[i+step] = arr[i] ^ arr[i+step];
arr[i] = arr[i] ^ arr[i+step];
flag = true;
count++;
}
i++;
}
}
System.out.println("combSort交换次数："+count+";分组次数："+count2);
}
} 冒泡排序性能之所以慢，是因为存在这样的一类问题
比如对数列 {9,8,7,6,5,4,3,2,1}进行升序排列
我们发现:
第一轮冒泡排序交换了 8次，结果{8,7,6,5,4,3,2,1,9}
第二轮冒泡排序交换了7次，结果{7,6,5,4,3,2,1,8,9}
第三轮冒泡排序交换了6次，结果{6,5,4,3,2,1,7,8,9}
........
最后经过8轮比较交换总共交换次数 8+7+6+5+4+3+2+1=36次
n个数据最大交换次数就是 (n-1)+(n-2)+...+3+2+1 = n(n-1)/2 ---->O(n^2) n平方量阶的时间复杂度，所以冒泡如果在数据很杂乱的情况下，时间消耗是很大的。
梳排序：梳排序的本质还是冒泡，只不过它对整个数列进行分组冒泡,可以类比希尔排序去理解
梳排序最终还是得进行一次完全的冒泡排序，但是呢在此前由于分组操作已经将元素基本上放好了，所以最后一次全体冒泡排序
我们看看梳排序对上述数列操作的效率
初始： step = length=9; flag = true;
判断：step>1，step如果=1说明内部做了一次完全冒泡排序了，那就没必要继续排了
第一次分组排序：
9>1；
flag = false;
step除以因子1.3，这个因子的选择只是为了让分组次数比较合适 并不是固定的 算法笔记这本书的介绍中，推荐了最合适的因子 1.3
step /1.3 --->6
进行组内冒泡排序 ----真正的分组 06,17,28 对三组分别冒泡
第一组：0 6号元素 也就是 9 3 冒泡：一次交换，排序后元素为{3,8,7,6,5,4,9,2,1}
第二组：1 7号元素 也就是 8,2 冒泡：一次交换，排序后元素为{3,2,7,6,5,4,9,8,1}
第三组：2 8号元素 也就是 7,1 冒泡：一次交换，排序后元素为{3,2,1,6,5,4,9,8,7}
最多只有8号元素 所以结束本次分组排序 总交换次数：3次 flag = true;
第二次分组排序：
6>1
6/=1.3--->4 flag = false;
进行组内冒泡排序---真正的分组：048,15,26,37 四组冒泡 对四组分别冒泡
以下是按照循环比较的逻辑:
第一组：0,4号元素，也就是3,5 不必交换
第二组：1,5号元素，也就是2,4 不必交换
第三组：2,6号元素，也就是1,9 不必交换
第四组：3,7号元素，也就是6,8 不必交换
第五组：4,8号元素，也就是5,7 不必交换
结束本次分组，总交换次数0 元素{3,2,1,6,5,4,9,8,7} flag = false;
第三次分组排序：
4>1 flag = false;
4/1.3---->3 真正的分组：036,147,258 三组 对三组分别冒泡
按照循环逻辑比较：
分组分别为 {0,3},{1,4},{2,5},{3,6},{4,7},{5,8}
对应元素为{3,6},{2,5},{1,4},{6,9},{5,8},{4,7}
结束分组，总交换次数0，元素{3,2,1,6,5,4,9,8,7} flag = false
第四次分组排序：
3>1 flag = false;
3/=1.3---->2 真正的分组：02468,1357 2组 对两组分别冒泡
按照循环逻辑比较：
分组分别为：
对应元素 一次交换结果
{0,2}---------------->{3,1}-------------------->{1,2,3,6,5,4,9,8,7} --->交换了一次
{1,3}---------------->{2,6}-------------------->{1,2,3,6,5,4,9,8,7}
{2,4}---------------->{3,5}-------------------->{1,2,3,6,5,4,9,8,7}
{3,5}---------------->{6,4}-------------------->{1,2,3,4,5,6,9,8,7}---->交换了一次
{4,6}---------------->{5,9}-------------------->{1,2,3,4,5,6,9,8,7}
{5,7}---------------->{6,8}-------------------->{1,2,3,4,5,6,9,8,7}
{6,8}---------------->{9,7}-------------------->{1,2,3,4,5,6,7,8,9}---->交换了一次
结束分组，总交换次数3 flag = true
此时其实已经排好序了
但是还会进行第五次分组，这是最后一次校验，进行一次完全冒泡，这时候已经不会再进行任何的交换了
step>1 flag =false
step/=1.3=1
完全冒泡分组：012345678 一组 flag = false
单个比较分组：01,12,23,34,45,56,67,78,89
总共交换次数才6次，远小于冒泡的36次交换，当数据很大的时候，这种性能差异会更明显 ===============================================================================================================================================
所以，咱们以后提到冒泡的时候，不要在说他性能差了。
良好的设计，也能够使冒泡排序有不亚于快排，希尔，桶排序等主流排序算法的性能。
记住这一个排序算法：
梳排序------分组冒泡排序
正浩创新EcoFlow公司福利 728人发布
