08.排序：冒泡，插入，选择

1.如何分析一个排序算法

1.排序算法的执行效率

最好情况，最坏情况，平均情况时间复杂度以及对应的要排序的原始数据；
时间复杂度的系数、常数和低阶。用于同一阶时间复杂度的比较；
比较次数和交换(移动)的次数
基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动
2.排序算法的内存消耗
是否是原地排序，即是否占用额外的内存空间；
3.排序算法的稳定性
如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变

2.冒泡排序(Bubble Sort)

image.png

public void bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        int len = arr.length;
        // 提前退出循环的标志
        boolean flag = true;
        // 外层循序：一共进行几次循环，len-1
        // 内层循环：每次循环需要几次比较，因为靠后的数字已经比较完了，不需要再次比较，直接跳过就可以
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = false;
                }
            }
            // 没有数据交换，直接结束
            if (flag) {
                break;
            }
        }
    }
    private void swap(int[] arr, int m, int n) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (m > arr.length - 1 || n > arr.length - 1) {
            return;
        }
        int tmp = arr[m];
        arr[m] = arr[n];
        arr[n] = tmp;
    }

自问自答：

冒泡排序是否是原地排序？--是的
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法
冒泡排序是否是稳定的排序吗？--是的
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
冒泡排序的时间复杂度是多少？
要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。
而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。
平均时间复杂度，引入逆序数的概念：
有序度是数组中具有有序关系的元素对的个数。
满有序度：n*(n-1)/2
逆序度：满有序度-有序度；
逆序度表示元素需要交换的次数，而比较的次数肯定高于交换的次数。

最坏情况下，初始状态的有序度是 0，所以要进行 n(n-1)/2 次交换。最好情况下，初始状态的有序度是 n(n-1)/2，就不需要进行交换。我们可以取个中间值 n(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。换句话说，平均情况下，需要 n(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n2)，所以平均情况下的时间复杂度就是 O(n2)。

3.插入排序

image.png

大体思想：将排序的数组分为已排序区域和待排序区域，然后每次从待排序区域里面选择一个元素进行与已排序区域的元素进行比较，这里比较的方式是从尾到头比较，如果待比较的值小于已排序的元素，则进行搬移，否则中断流程；同时注意临界情况的处理；

 public void insertSort(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        // 数组长度
        int n = arr.length;
        // 外层循环：定义已排序区域和未排序区域，默认第一个元素已经排序，故i从1开始
        for (int i = 1; i < n; i++) {
            // 待插入的元素，比较的元素从【0，i-1]
            int value = arr[i];
            int j = i - 1;
            // 内层循环，比较的元素从[i-1,0]倒序比较，符合的话break本次循环，不符合的话移动
            for (; j >= 0; j--) {
                if (arr[j] > value) {
                    // 为啥是j+1，因为在初始时，j+1=i，需要移动到这个位置，后面会依次有个空
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            // 空的位置是j+1
            arr[j + 1] = value;
        }
    }

插入排序是否是原地排序？--是的
不需要占用额外的数组空间
冒泡排序是否是稳定的排序吗？--是的
是的，在比较过程中，只有小于的元素才会移动，对于等于的情况不会移动
冒泡排序的时间复杂度是多少？
最好情况：直接排好序，遍历一次O(n)
最坏情况：每一次都要比较和移动，O(n2)
平均复杂度：数组中插入一个数据的平均时间复杂度是O(n)，那么遍历n次就是O(n2)
冒泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？
** 对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。**
但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个


冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序，需要 K 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时就是 3*K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。

选择排序

image.png

小结

image.png