交换排序之冒泡排序Bubble Sort

 

 概述

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

 

算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

动图

 

代码实现

第一种实现：

    原始的冒泡排序算法，性能差

/**
     * 冒泡排序的第一种实现, 没有任何优化
     *
     * @param source
     */
    public static void bubbleSort1(Integer[] source) {
        int i, j;
        int size = source.length;

        for (i = 0; i < size; i++) {//表示n次排序过程。
            for (j = 1; j < size - i; j++) {//i以后的都已经有序，不需要再排序
                if (source[j - 1] > source[j]) {//前面的数字大于后面的数字就交换
                    //交换a[j-1]和a[j]
                    int temp;
                    temp = source[j - 1];
                    source[j - 1] = source[j];
                    source[j] = temp;
                }
            }
        }
        print(source);
    }// end

 第二种实现：

  

/**
     * 冒泡排序的第二种实现, 当前一次排序没有调整顺序，说明已有序
     *
     * @param source
     */
    public static void bubbleSort2(Integer[] source) {
        int i, j;
        int size = source.length;
        boolean flag = false;//表示是否有调整顺序

        for (i = 0; i < size; i++) {//表示n次排序过程。
            flag = false;
            for (j = 1; j < size - i; j++) {//i以后的都已经有序，不需要再排序
                if (source[j - 1] > source[j]) {//前面的数字大于后面的数字就交换
                    flag = true;
                    //交换a[j-1]和a[j]
                    int temp;
                    temp = source[j - 1];
                    source[j - 1] = source[j];
                    source[j] = temp;
                }
            }
            if (!flag) {
                break;
            }
        }
        print(source);
    }// end

 第三种实现：

 

 /**
     * 冒泡排序的第三种实现, 针对序列后半部分基本有序的情况，可减少循环次数
     *
     * @param source
     */
    public static void bubbleSort3(Integer[] source) {
        int j, k;
        int flag = source.length;//记录最后交换的位置，也就是排序的尾边界

        while (flag > 0) {//排序未结束标志
            k = flag; //k 来记录遍历的尾边界
            flag = 0;

            for (j = 1; j < k; j++) {
                if (source[j - 1] > source[j]) {//前面的数字大于后面的数字就交换
                    //交换a[j-1]和a[j]
                    int temp;
                    temp = source[j - 1];
                    source[j - 1] = source[j];
                    source[j] = temp;

                    //表示交换过数据;
                    flag = j;//记录最新的尾边界.
                }
            }
        }

        print(source);
    }// end

 

测试:

public static void main(String[] args) {
        Integer[] data = {2, 5, 8, 10, 9, 22, 34, 7, 13, 16, 9};

        print(data);
        bubbleSort1(data);

        Integer[] data2 = {2, 5, 8, 10, 9, 22, 34, 7, 13, 16, 9};
        print(data2);
        bubbleSort2(data2);

        //后面已有序
        Integer[] data3 = {2, 5, 8, 10, 9, 22, 34, 7, 13, 16, 9, 36, 40, 43, 50};
        print(data3);
        bubbleSort3(data3);
    }

 

算法复杂度

• 时间复杂度 

   最好的情况， 即要排序的数据本身就是有序的，那么比较次数，根据最后改进的代码，可以推断出就是n-1次的比较，没有数据交换，时间复杂度为O(n)。当最坏的情况，即待排序表是逆序的况，此时需要比较n(n+1)/2次，并作等数量级的记录移动。因此，总的时间复杂度为O(n^2)。

• 空间复杂度

    由以上算法步骤分析，可轻易得知冒泡排序的空间复杂度为 O(n), 需要辅助空间 O(1)

 

算法稳定性

   在相邻元素相等时，并不需要交换它们的位置，所以，冒泡排序是稳定排序。

 

算法适用场景

  在算法优化中提到过，实际使用过程中，在大量数据的情况下几乎不适用冒泡排序。

冒泡排序思路简单，代码简单，特别适合小数据的排序。

但是，由于算法复杂度较高，在数据量大的时候不适合使用。

 

参考：

   https://www.cnblogs.com/onepixel/p/7674659.html