冒泡排序BubbleSort-算法积累

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

1、算法思想

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

2、代码实现

public static void bubbleSort(int[] source) {
        int length = source.length;
        for (int i = 0; i < length - 1; i++) { // N个数需N-1趟,每趟完成之后,较大元素将冒到数组最末端
            for (int j = 0; j < length - 1 - i; j++) { // 每趟需要比较N-i次比较
                if (source[j] > source[j + 1]) {
                    swap(source, j, j + 1);
                }
                // System.out.print("
外循环第" + (i + 1) + "次,内循环第" + (j + 1) + "次,排序结果：");
                // printArray(source);
            }
            System.out.println("");
        }
    }

3、算法分析

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

4、算法改进

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

本文再提供以下两种改进算法：

1）．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

 /**
     * 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。
     * 
     * 由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
     */
    public static void bubbleSort2(int[] source) {
        int high = source.length - 1;
        while (high > 0) { // high=0时证明最后一次进行交换的位置为0
            int pos = 0;// 每趟开始，无记录交换
            for (int i = 0; i < high; i++) {
                if (source[i] > source[i + 1]) {
                    swap(source, i, i + 1);
                    pos = i; // 有交换则令pos=i
                }
            }
            high = pos; // 每趟for循环结束，pos、length变更一次
            // System.out.println(high);
        }
    }

2）．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:

/**
     * 每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大值和最小值),
     * 
     * 从而使排序趟数几乎减少了一半。
     */
    public static void bubbleSort3(int[] source) {
        int low = 0;
        int high = source.length - 1;
        while (low < high) {
            for (int i = low; i < high; i++) { // 正向找最大
                if (source[i] > source[i + 1]) {
                    swap(source, i, i + 1);
                }
            }
            high--; // 一次for循环结束，最大数冒出
            for (int i = high; i > low; i--) { // 逆向找最小
                if (source[i] < source[i - 1]) {
                    swap(source, i, i - 1);
                }
            }
            low++;
        }
    }

swap

private static void swap(int[] source, int x, int y) {
        int temp = source[x];
        source[x] = source[y];
        source[y] = temp;
    }

源码地址：https://github.com/zxiaofan/Algorithm/blob/master/src/sort/BubbleSort.java