冒泡排序

1 .算法思想
冒泡排序是一种简单的交换类排序算法，能够将相邻的元素进行交换，从而逐步将待排序序列变成有序序列。冒泡排序的基本思想是：从头扫描待排序列，在扫描的过程中顺次比较相邻两个元素的大小。下面以升序为例介绍排序过程。

• 在第一趟排序中，对n个记录进行如下操作：

  • 对相邻的两个记录的关键字进行比较，如果逆序就交换位置。
  • 在扫描的过程中，不断向后移动两个相邻两个记录中关键字较大的记录。
  • 将待排序记录序列中最大的关键字记录交换到待排序记录序列的末尾，这也是最大关键字记录应在的位置。

• 然后进行第二趟排序，对前n-1个记录进行同样的操作，其结果是使次大的记录被放在第n-1个记录的位置上。

• 继续进行排序工作，在后面的排序中也反复遵循上述过程，直到排好序为止。如果在某一趟冒泡过程中没有发现一个逆序，就可以结束冒泡排序。

• 下面以一个例子演示一个完整的冒泡排序过程(从前向后冒泡)。

  • 待排序序列：69 65 90 37 92 6
  • 第 1 趟冒泡：65 69 37 90 6 92
  • 第 2 趟冒泡：65 37 69 6 90 92
  • 第 3 趟冒泡：37 65 6 69 90 92
  • 第 4 趟冒泡：37 6 65 69 90 92
  • 第 5 趟冒泡：6 37 65 69 90 92

2.算法实现

import java.util.Arrays;

/**
 * @Author: 落脚丶
 * @Date: 2017/10/17
 * @Time: 下午3:00
 * @ClassName: BubbleSort
 * @Description: 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int test[] = {49,38,97,76,13,27,34,12,64,5,62,99,98,54,56,
                18,23,15,35,51};
        bubbleSort(test);
        System.out.println(Arrays.toString(test));
    }
    public static void bubbleSort(int[] a) {
        boolean change = true;  // 标记是否发生交换
        for (int i = 1; i < a.length && change; i++) {
            change = false;
            for (int j = 0; j < a.length - 1; j++) {
                if (a[j] > a[j+1]) {
                    int tem = a[j+1];
                    a[j+1] = a[j];
                    a[j] = tem;
                    change = true;
                }
            }
        }
    }
}

3.算法复杂度分析
对于冒泡排序最坏的情况，即元素是逆序的，那么对于 n-1 趟冒泡则有:
   1+2+3+···+(n−1)=(n−1)n/2 =O(n²)(忽略if语句中的交换的时间)
最好的情况，输入已经是有序的序列，第二层 if 语句不执行(或者说只执行 1 次)。 故时间复杂度为:O(n)。平均情况：平均时间复杂度为 O(n²)。