基本思想
    冒泡排序的基本思想是对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动到数组前面，把大的元素移动到数组后面（交换两个元素的位置）。
    算法分析
    冒泡算法由双层循环实现。其外层循环用于控制排序轮数，即（i=arr.length）。而内层循环主要用于对比数组中每个相邻元素大小，以确定是否交换位置，对比和交换次数随排序轮数而减少，及（j=arr.length-1-i)。
    时间复杂度
    因此冒泡排序总的平均时间复杂度为：math.svg
    代码示例：

    1. /**
    2.  * 通过第三个临时变量方式，普通排序
    3.  * @param arr
    4.  */
    5. public static void sort(int[] arr) {
    6.     int temp = 0;
    7.     for (int i = 0; i < arr.length - 1; i++) {
    8.         for (int j = 0; j < arr.length - 1 - i; j++) {
    9.             if (arr[j] > arr[j + 1]) {
    10.                 temp = arr[j];
    11.                 arr[j] = arr[j + 1];
    12.                 arr[j + 1] = temp;
    13.             }
    14.         }
    15.     }
    16. }
    18. /**
    19.  * 两个数原地交换，不借助于第三个变量，实现两数交换
    20.  * @param arr
    21.  * @return
    22.  */
    23. public static void subtractSort(int[] arr) {
    24.     // 判断数组边界条件
    25.     if (arr==null||arr.length<2) return;
    26.     for (int i = 0; i < arr.length - 1; i++) {
    27.         for (int j = 0; j < arr.length - 1 - i; j++) {
    28.             if (arr[j] > arr[j + 1]) {
    29.                 arr[j] += arr[j + 1];
    30.                 arr[j + 1] = arr[j] - arr[j + 1];
    31.                 arr[j] -= arr[j + 1];
    32.             }
    33.         }
    34.     }
    35. }
    37. /**
    38.  * 按位异或方法，实现两数交换（效率更高推荐*****）
    39.  * 算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；
    40.  * @param arr
    41.  */
    42. public static void xorSort(int[] arr) {
    43.     // 判断数组边界条件
    44.     if (arr == null || arr.length < 2) return;
    45.     for (int i = 0; i < arr.length - 1; i++) {
    46.         for (int j = 0; j < arr.length - 1 - i; j++) {
    47.             if (arr[j] > arr[j + 1]) {
    48.                 arr[j] = arr[j] ^ arr[j + 1];
    49.                 arr[j + 1] = arr[j] ^ arr[j + 1];
    50.                 arr[j] = arr[j] ^ arr[j + 1];
    51.             }
    52.         }
    53.     }
    54. }

    优化问题

    • 针对问题：

    数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

    • 方案：

    设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
    这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

    1. /**
    2.  * 优化过后的冒泡排序
    3.  * @param arr
    4.  */
    5. public static void fastSort(int[] arr) {
    6.     // 判断数组边界条件
    7.     if (arr == null || arr.length < 2) return;
    8.     boolean flag = false;// 标识变量：记录是否交换
    9.     for (int i = 0; i < arr.length - 1; i++) {
    10.         for (int j = 0; j < arr.length - 1 - i; j++) {
    11.             if (arr[j] > arr[j + 1]) {
    12.                 flag = true;
    13.                 arr[j] = arr[j] ^ arr[j + 1];
    14.                 arr[j + 1] = arr[j] ^ arr[j + 1];
    15.                 arr[j] = arr[j] ^ arr[j + 1];
    16.             }
    17.         }
    18.         if (!flag) break;
    19.         else flag = false;//*****置为false
    20.     }
    21. }