排序算法 - 冒泡排序 | 王洪博's blog

基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法流程图

bubbleSortProcess

算法改进

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

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 冒泡排序
 */
public class BubbleSort {

    /**
     * 冒泡排序的过程很简单，就是不断比较相邻两个元素的大小关系，若逆序则交换，这样通过一轮比较，关子健最大的记录就沉底了。
     * 一般地，第i趟冒泡排序从第一个元素起到第n-i+1个元素依次比较相邻两个记录的关键字，并在逆序时交换相邻记录，其结果就是这n-i+1个记录中关键字最大的记录被交换到n-i+1的位置上。
     * 当然也可以反过来，从后往前进行，这样每经过一趟排序，就把未排序的序列中最小的元素放在它应当处于的位置上，然后下次比较就不再让前面的元素参与了。
     * 整个排序过程需要进行k趟冒泡排序，其中k至少为1，至多为n-1次，如果一趟冒泡排序中没有出现交换元素的操作，则说明序列已经有序了，可以停止排序了。
     * 时间复杂度：正序时O(n)， 逆序时O(n2)，平均时间复杂性O(n2)。使用temp 作为临时交换变量，空间复杂度为 O(1).
     * <p>
     * 一般情况下貌似效率不及直接插入排序（尽管它们的平均时间复杂度都是O(n2)）。
     */
    public static void bubbleSort(int[] numArr) {
        int length = numArr.length;
        //最多length-1次排序
        for (int i = 0; i < length; i++) {
            //每一轮多少元素参与排序
            for (int j = 0; j < length - 1 - i; j++) {
                if (numArr[j] > numArr[j + 1]) {
                    /**
                     * 交换顺序，不使用临时变量，利用
                     * a = a + b;
                     * b = a - b;
                     * a = a - b;
                     */
                    numArr[j] = numArr[j] + numArr[j + 1];
                    numArr[j + 1] = numArr[j] - numArr[j + 1];
                    numArr[j] = numArr[j] - numArr[j + 1];
                }
            }
        }
    }

    /**
     * 改进版冒泡：当某趟排序没有元素交换的时候，证明整个序列有序，无需再循环比较
     *
     * @param numArr
     */
    public static void bubbleSortImprove(int[] numArr) {
        int length = numArr.length;
        //设置标志变量，这样当序列有序时及时退出循环，避免冗余处理。
        boolean sorted = false;
        //最多length-1次排序
        for (int i = 0; i < length; i++) {
            sorted = true;
            //每一轮多少元素参与排序
            for (int j = 0; j < length - 1 - i; j++) {
                if (numArr[j] > numArr[j + 1]) {
                    /**
                     * 交换顺序，不使用临时变量，利用
                     * a = a + b;
                     * b = a - b;
                     * a = a - b;
                     */
                    numArr[j] = numArr[j] + numArr[j + 1];
                    numArr[j + 1] = numArr[j] - numArr[j + 1];
                    numArr[j] = numArr[j] - numArr[j + 1];
                    sorted = false;
                }
            }
            if (sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] numArr = {27, 11, 13, 45, 34, 22, 19, 8, 3, 99, 74, 55, 88, 66};
        System.out.println("**************冒泡排序******************");
        System.out.println("排序前：");
        CommonUtils.display(numArr);
        System.out.println("排序后：");
        bubbleSortImprove(numArr);
        CommonUtils.display(numArr);
    }
}

CommonUtils工具类：

package main.java.com.study.utils;

/**
 * @author: whb
 * @description: 工具类
 */
public class CommonUtils {

    /**
     * 遍历打印
     *
     * @param numArr
     */
    public static void display(int[] numArr) {
        if (numArr != null && numArr.length > 0) {
            for (int num : numArr) {
                System.out.print(num + "  ");
            }
        }
        System.out.println("");
    }
}

测试结果

冒泡排序测试