排序算法：冒泡排序

什么是冒泡排序？

冒泡排序是一种最基础的交换排序，它就是把相邻的元素两两进行比较，根据大小来交换元素的位置，把较小的元素放在前面较大的元素放在后面，重复‘比较’‘交换’操作，最终实现数组有序的效果。

原理图如下：

实现步骤：

（1） 比较相邻两个元素的大小，然后把较小的数放在前面，较大的数放在后面。

（2） 经过n-1次比较后，最大的那个元素会沉到数组中第n-1个的位置

（3） 如果n-1大于0，就继续重复1，2 否则排序完成。

时间复杂度：

该排序算法在最好情况下（元素是完全有序的）时间复杂度是O(n)，最坏情况下（元素是完全逆序的）时间复杂度是O(n2)。 冒泡排序、选择排序、插入排序时间复杂度都是O（n2）

稳定性：

数组中相同的值，经过排序后位置不变表示该排序算法是稳定的，否则是不稳定的。冒泡排序和插入排序是稳定排序，选择排序是不稳定排序。

冒泡排序第一版：

public static int[] bubbleSort(int[] arr) {
   for (int i = 0; i < arr.length; i++) {
       for (int j = 0; j < arr.length - i - 1; j++) {
           if (arr[j] > arr[j + 1]) {
               int temp = 0;
               temp = arr[j];
               arr[j] = arr[j+1];
               arr[j+1] = temp;
           }
       }
   }
   return arr;
}

冒泡排序优化

上面代码只是冒泡排序最简单的实现方式，其实冒泡排序有很大可以优化的空间。有时候我们会发现，经过几轮排序后，整个数组已经是有序的了。但是外层循环还在继续工作。比如 5，8，6，3，9，2，1，7 这个数组在进行最后几轮的排序时是下图这样的。那么能不能判断数组已经有序后，就直接结束循环，减少循环次数呢？往下看

冒泡排序第二版：

public static int[] bubbleSortUp(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 是否有元素交换标记
        boolean isSorted  = true;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = 0;
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                // 如果有元素交换,就赋值为false
                isSorted  = false;
            }
        }
        if (isSorted) {
            break;
        }
    }
   return arr;
}

在上面的代码中，我们加了一个标记是否有元素交换的标记，如果有元素交换说明排序还没有完成，如果没有说明数组已经是有序的就结束循环，完成排序。

冒泡排序再优化

按照上面的逻辑，始终是有序区的长度和排序的轮数相等。但是实际上数组真正的有序区可能会大于这个长度，比如这个数组（3，4，2，1，5，6，7，8），通过观察可以发现数组后半段已经是有序的了，我们只需要对无序区排序就可以了，但是按照上面的逻辑，我们还要把有序区也加进来进行排序，这是完全没必要的。我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

冒泡排序第三版：

public static int[] bubbleSortPlus(int[] arr) {
    int temp = 0;
    // 记录无序边界的位置
    int unSortedIndex = arr.length - 1;
    // 记录最后一次数据交换的位置
    int lastDataChangeIndex = 0;
    for (int i = 0; i < arr.length; i++) {
        boolean isSorted  = true;
        for (int j = 0; j < unSortedIndex; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                // 如果有元素交换,就赋值为false
                isSorted  = false;
                // 最后一次元素交换的位置
                lastDataChangeIndex = j;
            }
        }
        unSortedIndex = lastDataChangeIndex;
        if (isSorted) {
            break;
        }
    }
    return arr;
}

这一版代码中，unSortedIndex就是无序数列的边界。每一轮排序过程中，unSortedIndex之后的元素就完全不需要比较了，肯定是有序的。

注：本文大部分内容来自程序员小灰的公众号，我只是一个搬到这用来加深自己记忆的，在此向小灰大神致敬！

原文链接：https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653194666&idx=1&sn=69ce32870c0b981c40b1e124fbb6bba8&chksm=8c99fb70bbee72668cad223892ad362525d215e7f936458f99dd289eb82981099359310e9e54&scene=21#wechat_redirect

排序算法：冒泡排序

原文：https://www.cnblogs.com/soooohappy/p/12577969.html