图解冒泡、选择和插入排序

代码实现（以升序为例）：

public static int[] bubbling(int[] arr) {
    int len = arr.length;
    if(len<=1){
        return arr;
     }


      boolean flag=false;//标记是否有元素交换，默认为false
    int tmp = 0;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                flag=true;
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
        //如果内层循环未进行交换，即已排好序，直接结束；否则重置flag，继续循环。
        if (!flag) {
            break;
        }else {
            flag=false;
        }
    }
    return arr;
}

下面用开始讲的分析方法分析一下冒泡排序的好坏：

(1)冒泡排序是否是原地排序算法

    冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

(2)冒泡排序是否是稳定排序算法

    冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

(3)冒泡排序的时间复杂度是多少

    最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作（即遍历n个元素），就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n^2)。

平均时间复杂度：

    这里分析平均时间复杂度，通过“有序度”和“逆序度”这两个概念来进行分析。有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：

有序元素对：a[i] <= a[j], 如果i < j。

    按升序排列来讲，就是一对元素，下标大的元素数据值也大，那么这两个元素就是有序元素对。如：

[3,7,1,4,9] 这组数据的有序度为：7
其有序元素对有7对，分别为：
(3,7),(3,4),(3,9),(7,9),(1,4),(1,9),(4,9)

    同理，对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。

逆序度的定义正好跟有序度相反（默认从小到大为有序）

[3,7,1,4,9] 这组数据的逆序度为：3
其逆序元素对有3对，分别为：
(3,1),(7,1),(7,4)

    根据上面的分析，可以得到一个公式：逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

    冒泡排序包含两个原子操作，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2——初始有序度。此例中就是 10–7=3，要进行 3次交换操作。

    对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。

    换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n^2)，所以平均情况下的时间复杂度就是 O(n^2)。这个平均时间复杂度推导过程并不严格，但是很多时候很实用。

三、插入排序

    顾名思义，插入排序是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。插入排序是一种内部排序。

思路分析：

    把n个待排序的元素看成为一个有序和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

图解：

    对于一组元素[34,101,231,10,78,99]，其中有序列表为[34,101,231]，无序列表为[10,78,99]。假设现在要插入的数据为10，下面演示一下插入的过程：

①先把10保存到insertVal，然后前一个位置为insertIndex=2

②由于arr[insertIndex](231) > insertVal(10)，且insertIndex=2>=0，把231赋值给后一个位置，insertIndex-1=1，指向101

③由于arr[insertIndex](101) > insertVal(10)，且insertIndex=1>=0，把101赋值给后一个位置，insertIndex-1=0，指向34

④由于arr[insertIndex](34) > insertVal(10)，且insertIndex=0=0，把34赋值给后一个位置，insertIndex-1=-1

⑤由于insertIndex<0，所以找到了插入位置，即insertVal的位置为insertIndex+1=-1+1=0，然后将insertVal赋值给下标为0的位置

至此，一个待插入的数就完成了 插入，然后依次插入后续的数即可

代码实现：

public static int[] insertSort(int[] arr) {
    for (int i =1;i<arr.length;i++) {
        //定义插入的数，从数组第2个数开始
        int insertVal = arr[i];
        //定义插入位置，从插入数的前一个位置坐标开始依次往前判断
        int insertIndex = i - 1;
        //给insertVal找到插入的位置
        //说明：
        //1.insertIndex>=0保证插入位置下标不越界
        //2.arr[insertIndex] > insertVal 待插入的数小于前面的数，说明还没找到插入位置
        //（因为是升序排，所以待插入值前面的值都是升序排好的，所以只要找到前面数小于待插入数时即找到位置）
        //3.需要将arr[insertIndex]后移：arr[insertIndex + 1] = arr[insertIndex]
        //4.insertIndex前移继续找位置
        while (insertIndex >= 0 && arr[insertIndex] > insertVal) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        //当退出while循环时，说明insertVal的位置已经找到，就是insertIndex+1
        arr[insertIndex + 1] = insertVal;
    }
    return arr;
}

    在上面的例子中，我们采用的是从尾到头查找插入点的方法，当然也可以用从头到尾查找的方法，对于这两种方法，元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

    拿我们上面的一组元素 [34,101,231,10,78,99] 来说，满有序度为n*(n-1)/2=15，初始序列的有序度是 8，所以逆序度是 7。插入排序中，数据移动的个数总和也等于 7=3+2+2。

思路分析：

    选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。直到未排序区间中只剩一个为止，这个元素就是这组元素的最大值，这时完成排序。

图解：

public static int[] selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;//最小值的下标
        int min = arr[i];//最小值
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j;
            }
        }
        if (minIndex != i) {//如果最小值下标发生了改变，需要交换arr[i]和arr[minIndex]的值
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }
    return arr;
}