文档章节

java冒泡排序

YY小苹果
 YY小苹果
发布于 2017/04/13 21:05
字数 1536
阅读 9
收藏 0

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

原理:比较两个相邻的元素,将值大的元素交换至右端。

思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。重复第一趟步骤,直至全部排序完成。

下面代码可直接拷贝到编译器运行认证

1、冒泡排序简易版

package sort;

import java.util.Arrays;

/**
 * 冒泡排序简易版,每一趟都是5次比较,第一次以后的都有重复的比较
 * 第1趟比较
    第1次[8, 9, 4, 5, 7, 2]
    第2次[8, 4, 9, 5, 7, 2]
    第3次[8, 4, 5, 9, 7, 2]
    第4次[8, 4, 5, 7, 9, 2]
    第5次[8, 4, 5, 7, 2, 9]
        第2趟比较
    第1次[4, 8, 5, 7, 2, 9]
    第2次[4, 5, 8, 7, 2, 9]
    第3次[4, 5, 7, 8, 2, 9]
    第4次[4, 5, 7, 2, 8, 9]
    第5次[4, 5, 7, 2, 8, 9]
       第3趟比较
    第1次[4, 5, 7, 2, 8, 9]
    第2次[4, 5, 7, 2, 8, 9]
    第3次[4, 5, 2, 7, 8, 9]
    第4次[4, 5, 2, 7, 8, 9]
    第5次[4, 5, 2, 7, 8, 9]
       第4趟比较
    第1次[4, 5, 2, 7, 8, 9]
    第2次[4, 2, 5, 7, 8, 9]
    第3次[4, 2, 5, 7, 8, 9]
    第4次[4, 2, 5, 7, 8, 9]
    第5次[4, 2, 5, 7, 8, 9]
       第5趟比较
    第1次[2, 4, 5, 7, 8, 9]
    第2次[2, 4, 5, 7, 8, 9]
    第3次[2, 4, 5, 7, 8, 9]
    第4次[2, 4, 5, 7, 8, 9]
    第5次[2, 4, 5, 7, 8, 9]
 * 
 * @author Administrator
 *
 */
public class BubbleSort1 {
    public static void main(String[] args) {
        int[] arr = { 8, 9, 4, 5, 7, 2 };
        sort(arr);
    }

    /**
     * 
     * 冒泡排序方法
     * 
     * @param arr
     */
    public static void sort(int[] arr) {
        int len = arr.length;// 数组长度
        for (int i = 0; i < len - 1; i++) {
            System.out.println("第" + (i + 1) + "趟比较");
            for (int j = 0; j < len - 1; j++) {
                System.out.print("第" + (j + 1) + "次");
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

2、冒泡排序优化版

package sort;

import java.util.Arrays;

/**
 * 冒泡排序优化版:比较一趟就可以少一次比较,因为前面已经比较过的就不用比较了
 *     第1趟比较
        第1次[8, 9, 4, 5, 7, 2]
        第2次[8, 4, 9, 5, 7, 2]
        第3次[8, 4, 5, 9, 7, 2]
        第4次[8, 4, 5, 7, 9, 2]
        第5次[8, 4, 5, 7, 2, 9]
    第2趟比较
        第1次[4, 8, 5, 7, 2, 9]
        第2次[4, 5, 8, 7, 2, 9]
        第3次[4, 5, 7, 8, 2, 9]
        第4次[4, 5, 7, 2, 8, 9]
            //第5次[4, 5, 7, 2, 8, 9]   8和9在第一趟的第一次已经比较过了,所以可以去掉
    第3趟比较
        第1次[4, 5, 7, 2, 8, 9]
        第2次[4, 5, 7, 2, 8, 9]
        第3次[4, 5, 2, 7, 8, 9]
            //第4次[4, 5, 2, 7, 8, 9]   
            //第5次[4, 5, 2, 7, 8, 9]          同理前面都比较过了
    第4趟比较
        第1次[4, 5, 2, 7, 8, 9]
        第2次[4, 2, 5, 7, 8, 9]
            //第3次[4, 2, 5, 7, 8, 9]
            //第4次[4, 2, 5, 7, 8, 9]
            //第5次[4, 2, 5, 7, 8, 9]         同理前面都比较过了
    第5趟比较
        第1次[2, 4, 5, 7, 8, 9]
            //第2次[2, 4, 5, 7, 8, 9]
            //第3次[2, 4, 5, 7, 8, 9]
            //第4次[2, 4, 5, 7, 8, 9]
            //第5次[2, 4, 5, 7, 8, 9]  同理前面都比较过了
 * 
 * @author Administrator
 *
 */
public class BubbleSort2 {
    public static void main(String[] args) {
        int[] arr = { 8, 9, 4, 5, 7, 2 };
        sort(arr);
    }

    /**
     * 
     * 冒泡排序方法
     * 
     * @param arr
     */
    public static void sort(int[] arr) {
        int len = arr.length;// 数组长度
        for (int i = 0; i < len - 1; i++) {
            System.out.println("第" + (i + 1) + "趟比较");
            for (int j = 0; j < len - 1 - i; j++) {        //每比较一趟完后,就少一次比较,因为前面已经比较过了
                System.out.print("第" + (j + 1) + "次");
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

3、冒泡排序最终版

package sort;

import java.util.Arrays;

/**
 * 冒泡排序最终版:如果有的数组已经有顺序了,那就直接停止排序
 * @author Administrator
 *
 */
public class BubbleSort3 {

    //两个版本比较,最终版比较的趟数更少
    public static void main(String[] args) {
        
        int[] arr = { 1, 9, 4, 5, 7, 10 };
        System.out.println("---------优化版--------");
        sort2(arr);    //优化版 
        
        
        arr =new int[]{ 1, 9, 4, 5, 7, 10 };
        System.out.println("---------最终版--------");
        sort1(arr);   //最终版
    }

    /**
     * 
     * 冒泡排序最终版方法
     * 
     * @param arr
     */
    public static void sort1(int[] arr) {
        int len = arr.length;// 数组长度
        boolean sorted = true;   //用于标识数组是否有序
        for (int i = 0; i < len - 1; i++) {
            sorted =true;        //每一趟比完之后都假设数组已经有序
            System.out.println("第" + (i + 1) + "趟比较");
            for (int j = 0; j < len - 1 - i; j++) {        //每比较一趟完后,就少一次比较,因为前面已经比较过了
                System.out.print("第" + (j + 1) + "次");
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    sorted = false;    //如果进入比较,就说明数组还是无序,还需要比较   ,上面的假设失败
                }
                System.out.println(Arrays.toString(arr));
            }
            
            //每一趟比较完之后,判断数组是否已经有序,如果有序,那么就直接跳出循环,这样就可以减少比较的趟数
            if(sorted==true){
                break;
            }
            
        }
        System.out.println(Arrays.toString(arr));
    }
    
    
    
    /**
     * 
     * 冒泡排序优化版方法
     * 
     * @param arr
     */
    public static void sort2(int[] arr) {
        int len = arr.length;// 数组长度
        for (int i = 0; i < len - 1; i++) {
            System.out.println("第" + (i + 1) + "趟比较");
            for (int j = 0; j < len - 1 - i; j++) {        //每比较一趟完后,就少一次比较,因为前面已经比较过了
                System.out.print("第" + (j + 1) + "次");
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

 

© 著作权归作者所有

YY小苹果
粉丝 0
博文 1
码字总数 1536
作品 0
丰台
程序员
私信 提问

暂无文章

day13static-final

静态变量的特点:只加载一次,不会随着对象的创建而增加

architect刘源源
45分钟前
1
0
分而治之-快速排序

快速排序的思想: 快速排序首先在数组中确定1个枢纽项(比如数组中的第一个元素),将大于该枢纽项的元素放到右侧,小于该枢纽项的元素放到左侧,这样枢纽项将数组划分成两部分。接着继续对划...

万山红遍
今天
4
0
Qt编写自定义控件9-导航按钮控件

前言 导航按钮控件,主要用于各种漂亮精美的导航条,我们经常在web中看到导航条都非常精美,都是html+css+js实现的,还自带动画过度效果,Qt提供的qss其实也是无敌的,支持基本上所有的CSS2属...

飞扬青云
今天
3
0
Python开发工具:pyJasper

原文:https://www.oschina.net/p/pyjasper 前言 pyJasper是 JasperReports 网络服务器的 Python 客户端。 pyJasper 是一组 Python 基础工具,可以用来处理 JasperReports 报表 。因为 Jasper...

A_裙232550246
今天
2
0
如何提高使用Java反射的效率?

前言 在我们平时的工作或者面试中,都会经常遇到“反射”这个知识点,通过“反射”我们可以动态的获取到对象的信息以及灵活的调用对象方法等,但是在使用的同时又伴随着另一种声音的出现,那...

花漾年华
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部