排序算法之冒泡排序改进算法

栏目: 编程工具 · 发布时间: 6年前

内容简介:排序算法中最最常见也算是入门的一个排序算法就是冒泡排序。这篇文章我们就来好好地写写这个冒泡排序算法,以及冒泡排序呢的改进算法。既然普通的冒泡排序只适合用于排序入门,那这冒泡排序是否可以进行改进进行实际应用呢?这里我们就来进行冒泡排序改进。上面的比较次数非常的不合理,就算是正常的有序依然会进行比较N*(N-1)/2次,那我们就可以通过标记当前已经有序则停止进行后续无用的比较,跳出循环。具体代码如下:上面的改进方法,是根据上一轮排序有没有发生数据交换作为标识,进一步思考,如果上一轮排序中,只有后一段的几个元素

前言

排序算法中最最常见也算是入门的一个 排序 算法就是冒泡排序。这篇文章我们就来好好地写写这个冒泡排序算法,以及冒泡排序呢的改进算法。

传统冒泡算法

static int[] array = {100,1,5,4,11,2,20,18,89,34,20,34};
@Test
    public  void bubbleSortNormal(){
        int temp;
        int len = array.length;

        for(int i=0;i<len-1;i++){
            for(int j=1;j<len-i;j++){
                if(array[j-1]>array[j]){
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }
            }
            System.out.print("第"+(i+1)+"轮排序结果:");
            display();
        }
    }
排序算法之冒泡排序改进算法

分析:

上面的算法代码非常好理解,我们现在来分析一下这个算法的时间复杂度:

(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2;

因为只有在前面的元素比后面的元素大时才交换数据,所以交换的次数少于比较的次数。如果数据是随机的,大概有一半数据需要交换,则交换的次数为N^2/4(不过在最坏情况下,即初始数据逆序时,每次比较都需要交换)。

交换和比较的操作次数都与N^2成正比,由于在大O表示法中,常数忽略不计,冒泡排序的时间复杂度为O(N^2)。

O(N^2)的时间复杂度是一个比较糟糕的结果,尤其在数据量很大的情况下。所以普通冒泡排序通常不会用于实际应用。

改进冒泡排序版本1

既然普通的冒泡排序只适合用于排序入门,那这冒泡排序是否可以进行改进进行实际应用呢?这里我们就来进行冒泡排序改进。上面的比较次数非常的不合理,就算是正常的有序依然会进行比较N*(N-1)/2次,那我们就可以通过标记当前已经有序则停止进行后续无用的比较,跳出循环。具体代码如下:

static int[] array = {100,1,5,4,11,2,20,18,89,34,20,34};
   @Test
    public void bubbleSortPlusOne(){
        int temp;
        int len = array.length;
        for(int i=0;i<len-1;i++){
            boolean exchange = false;
            for(int j=1;j<len-i;j++){
                //如果前一位大于后一位,交换位置
                if(array[j-1]>array[j]){
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;

                    //发生了交换操作
                    if(!exchange){ exchange =true;}
                }
            }
            System.out.print("第"+(i+1)+"轮排序结果:");
            display();
            //如果上一轮没有发生交换数据,证明已经是有序的了,结束排序
            if(!exchange){ break;}
        }
    }
排序算法之冒泡排序改进算法

分析:

加入标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。

进一步升级冒泡排序

上面的改进方法,是根据上一轮排序有没有发生数据交换作为标识,进一步思考,如果上一轮排序中,只有后一段的几个元素没有发生数据交换,是不是可以判定这一段不用在进行比较了呢?答案是肯定的。

@Test
    public void bubbleSortImprovement(){
        int temp;
        int counter = 1;
        int endPoint = array.length-1;

        while(endPoint>0){
            int pos = 1;
            for(int j=1;j<=endPoint;j++){
                if(array[j-1]>array[j]){
                    temp= array[j-1];
                    array[j-1]= array[j];
                    array[j]= temp;

                    pos= j;
                }
            }
            endPoint= pos-1;

            System.out.print("第"+counter+"轮排序结果:");
            display();
            counter++;
        }
    }
排序算法之冒泡排序改进算法

分析:

设置一个pos指针,pos后面的数据在上一轮排序中没有发生交换,下一轮排序时,就对pos之后的数据不再比较。

冒泡排序改进

我们是否可以通过正向找寻最大值,反向找寻最小值把这个排序完成呢?答案是肯定的,接下来我们通过算法进行分析:

@Test
    public void bubbleSortImprovementPlus(){
        int temp;
        int low = 0;
        int high = array.length-1;
        int counter = 1;
        while(low<high){

            for(int i=low;i<high;++i){
                if(array[i]>array[i+1]){
                    temp= array[i];
                    array[i]= array[i+1];
                    array[i+1]= temp;
                }
            }
            --high;

            for(int j=high;j>low;--j){
                if(array[j]<array[j-1]){
                    temp= array[j];
                    array[j]= array[j-1];
                    array[j-1]= temp;
                }
            }
            ++low;

            System.out.print("第"+counter+"轮排序结果:");
            display();
            counter++;
        }
    }
排序算法之冒泡排序改进算法

分析:

传统的冒泡算法每次排序只确定了最大值,我们可以在每次循环之中进行正反两次冒泡,分别找到最大值和最小值,如此可使排序的轮数减少一半。

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-11/155585.htm


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

信息检索导论

信息检索导论

Christopher D.Manning、Hinrich Schütze、Prabhakar Raghavan / 王斌 / 人民邮电出版社 / 201008 / 69.00元

封面图片为英国伯明翰塞尔福瑞吉百货大楼,其极具线条感的轮廓外型优美,犹如水波的流动。其外表悬挂了1.5万个铝碟,创造出一种极具现代气息的纹理装饰效果,有如夜空下水流的波光粼粼,闪烁于月光之下,使建筑的商业氛围表现到极致。设计该建筑的英国“未来系统建筑事物所”,将商场内部围合成一个顶部采光的中庭,配以交叉的自动扶梯,使购物环境呈现出一种凝聚的向心力和商业广告的展示效应。作为英国第二商业城市伯明翰的建......一起来看看 《信息检索导论》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具