冒泡排序真的性能差吗

一个被人遗忘的排序算法-梳排序(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次交换,当数据很大的时候,这种性能差异会更明显
===============================================================================================================================================
所以,咱们以后提到冒泡的时候,不要在说他性能差了。
良好的设计,也能够使冒泡排序有不亚于快排,希尔,桶排序等主流排序算法的性能。
记住这一个排序算法:
        梳排序------分组冒泡排序
全部评论

相关推荐

4 收藏 评论
分享
牛客网
牛客企业服务