冒泡排序算法的实现和优化~-创新互联

冒泡排序算法: 算法思想:

反复扫描待排序记录序列,在扫描的过程中,顺次比较相邻的两个元素的大小,若逆序就交换位置

创新互联是一家集网站建设,金水企业网站建设,金水品牌网站建设,网站定制,金水网站建设报价,网络营销,网络优化,金水网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。文字描述该算法:

以升序为例:

依次比较数组中相邻两个元素大小,若a[j]>a[j+1],则交换两个元素,两两都比较一遍称为一轮冒泡,结果是让大的元素排至最后,重复该步骤,直至整个数组称为一个升序数组

初步实现:
package bin_find;
import java.util.Arrays;

public class bubble_sorted {public static void main(String[] args) {int arr[]={3,19,10,21,1,87,55,34};
        bubble(arr);
    }
    
    //冒泡排序的过程
    public static void bubble(int[] arr){//本次冒泡排序的目的是将数组的元素从小到大排序
        for(int j=0;j//控制要进行冒泡排序的次数--->n个数进行冒泡排序需要进行n-1轮
            for (int i = 0; i< arr.length - 1; i++){//一次for完成一轮排序
                if (arr[i] >arr[i + 1]) {//前者大于后者--->交换位置
                    swap(arr, i, i + 1);
                }
                 System.out.println("比较的次数为"+(i+1));
            }
            System.out.println("第"+(j+1)+"轮冒泡排序结果"+Arrays.toString(arr));
        }
    }
    
    //冒泡排序----核心算法
    public static void swap(int[] a,int i,int j){int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

输出如下所示:

比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[3, 10, 19, 1, 21, 55, 34, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第2轮冒泡排序结果[3, 10, 1, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第3轮冒泡排序结果[3, 1, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第4轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第5轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第6轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第7轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
优化版本1:减少冒泡次数

方法如下:

在这里插入图片描述

输出:

比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[3, 10, 19, 1, 21, 55, 34, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
第2轮冒泡排序结果[3, 10, 1, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
第3轮冒泡排序结果[3, 1, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
第4轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
第5轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
第6轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
第7轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
优化版本2:减少比较次数 方式1:

对于第一次到的优化输出结果,细心的小伙伴应该都发现了,其实第五次数组就已经是有序数组了,而最后两次元素之间的次序并没有任何的变化,这无疑增加了不必要的比较次数,那么接下来,我们通过判断该数组是否还存在元素交换,进而去确定,它是否需要进行下一轮的排序。

代码如下:

package bin_find;
import java.util.Arrays;

public class bubble_sorted {public static void main(String[] args) {int arr[]={3,19,10,21,1,87,55,34};
        bubble(arr);
    }

    //冒泡排序的过程
    public static void bubble(int[] arr){for(int j=0;jboolean swapped=false;
            for (int i = 0; i< arr.length - 1-j; i++){if (arr[i] >arr[i + 1]) {swap(arr, i, i + 1);
                    swapped=true;//只要某一轮中有进行交换的现象----将该变量设置为true
                }
                System.out.println("比较的次数为"+(i+1));
            }
            System.out.println("第"+(j+1)+"轮冒泡排序结果"+Arrays.toString(arr));
            //若swapped此时还为false:说明一轮冒泡结束,没有任何的两个元素发生交换---说明该数组已经变为有序数组
            if (!swapped){break;
            }
        }
    }

    //冒泡排序----核心算法
    public static void swap(int[] a,int i,int j){int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

输出如下:

比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[3, 10, 19, 1, 21, 55, 34, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
第2轮冒泡排序结果[3, 10, 1, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
第3轮冒泡排序结果[3, 1, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
第4轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]
比较的次数为1
比较的次数为2
比较的次数为3
第5轮冒泡排序结果[1, 3, 10, 19, 21, 34, 55, 87]

对比第一次的优化结果,我们会发现,比较次数整整少了两次,这里我们的好像还不能完全体现出该优化的优点,但是在原本就是有序数组的情况下,我们就能够体会到这个优点

举例:

对于任意的有序数组:

int arr[]={1,2,3,4,5,6,7,8};

输出如下:

它只比较了一次!

比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
第1轮冒泡排序结果[1, 2, 3, 4, 5, 6, 7, 8]
方式2:

对于某些数组,当第一轮排序过后,可能不仅是一个元素到达了最终的位置,也许是好几个,如下所示的这种情况:

在这里插入图片描述

当第一轮比较完成之后,我们会发现元素7 8 9都已经到达了最终的位置,那么第二轮乃至以后在比较的过程中,大可不必比较这三个元素的的大小,但是我们要怎么才能实现呢?

优化方式为:每轮冒泡时,最后一次交换索引可以作为下一轮冒泡的比较次数,如果这个值为0,表示整个数组有序,直接退出外层循环,结束冒泡排序

拿上面这种情况解释,也就是说,下一次,我们第一轮结束之际,需要记录元素3的索引,也就是4,第二轮比较的时候,只需要将前五个元素一一进行比较。

代码如下:

package bin_find;
import java.util.Arrays;

public class bubble_sorted {public static void main(String[] args) {int arr[]={5,2,7,4,1,3,8,9};
        bubble(arr);
    }

    //冒泡排序的过程
    public static void bubble(int[] arr){int n=arr.length-1;
        while (true){//用于记录最后一次交换时,较小索引的值,由于last的值在不断的变化,因此使用变量n进行记录
            int last=0;
            for (int i = 0; i< n; i++){//n即为下一次参与比较的元素个数,即为本轮last的值
                if (arr[i] >arr[i + 1]) {swap(arr, i, i + 1);
                    last=i;//由于是较小索引的值,因此将i赋值给last,而不是i+1
                }
                System.out.println("比较的次数为"+(i+1));
            }
            System.out.println("冒泡排序结果"+Arrays.toString(arr));
            n=last;
            if (n==0){//表示结束排序
                break;
            }
        }
    }

    //冒泡排序----核心算法
    public static void swap(int[] a,int i,int j){int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

输出如下:

我们会发现第二次只比较了4次,也就是前5个元素参与比较并进行排序了

比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
比较的次数为5
比较的次数为6
比较的次数为7
冒泡排序结果[2, 5, 4, 1, 3, 7, 8, 9]
比较的次数为1
比较的次数为2
比较的次数为3
比较的次数为4
冒泡排序结果[2, 4, 1, 3, 5, 7, 8, 9]
比较的次数为1
比较的次数为2
比较的次数为3
冒泡排序结果[2, 1, 3, 4, 5, 7, 8, 9]
比较的次数为1
比较的次数为2
冒泡排序结果[1, 2, 3, 4, 5, 7, 8, 9]

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章题目:冒泡排序算法的实现和优化~-创新互联
标题路径:http://scyanting.com/article/cejisd.html