冒泡排序

• 比较相邻两个数据，看是否满足大小关系，如不满足，则交换。一次冒泡至少会让一个元素移动到应该的位置上，重复 n 次，即可完成（本质上，也是将数据分为已排序区间和未排序区间）
• 优化：如果某次冒泡操作没有任何数据交换，则可知数据已经保持有序，可以提前退出
• 涉及操作：比较和交换，每交换一次，有序度加 1。对于给定数组，交换次数总是确定的，等于初始逆序度，而比较次数一定大于等于交换次数

稳定性：稳定，只要交换会改变两个元素前后顺序，因此当相邻元素大小相等时，不做交换

内存消耗：O(1) ，只涉及相邻数据交换，属于原地排序算法

执行效率：（1）最优 O(n) ：数据初始已经有序；（2）最差 O(n^2) ：数据初始完全逆序；（3）平均 O(n^2) ：最差情况，初始有序度为 0 ，需要经过 n(n-1)/2 次交换。最好情况，初始有序度即为满有序度，需要 0 次交换，取中间值 n(n-1)/4 。比较次数肯定大于等于交换，因而平均时间为 O(n^2)

有序度与逆序度

• 有序度：数组中具有有序关系的元素对的个数。完全有序的数组，具有满有序度，为 n(n-1)/2
• 逆序度：数组中具有逆序关系的元素对的个数。逆序度 = 满有序度 - 有序度

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean flag;  // 本次冒泡是否有数据交换，用于判定是否提前退出
    for (int i = 0; i < n; i++) {
        flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                flag = true;
            }
        }
        if (!flag) break;
    }
}

插入排序

• 将数据分为两个区间，即已排序区间和未排序区间，初始已排序区间只包含第一个元素。核心思想：取未排序区间元素，在已排序区间中寻找合适插入点
• 涉及操作：比较和移动，对于给定序列，根据不同的插入点查找方法（从前向后，从后向前），比较次数不同，但是移动次数是固定的，等于初始逆序度

稳定性：稳定，对于大小相同元素，可以选择将后面的元素插入到前面出现过的元素后面，保持前后顺序

内存消耗：O(1) ，不需要任何额外空间，属于原地排序算法

执行效率：（1）最优 O(n) ：数据初始已经有序，寻找插入点时，使用从尾到头查找；（2）最差 O(n^2) ：数据初始完全逆序，每次都需要插入第一个位置，大量移动操作；（3）平均 O(n^2) ：数组中插入一个数据的平均复杂度为 O(n) ，相当于需要循环执行插入操作 n 次

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int val = arr[i];
        int j = i - 1;
        while (j >= 0) {
            if (val < arr[j]) {
                arr[j+1] = arr[j];
                j--;
            } else {
                break;
            }
        }
        arr[j+1] = val;
    }
}

选择排序

• 类似插入排序，将数据分为已排序区间和未排序区间，每次从未排序区间中选择最小的元素，通过交换，将其放到已排序区间的末尾
• 涉及操作：比较和交换，对于给定数据，每次循环都会完整执行，因此比较次数是固定的，交换次数不一定

稳定性：不稳定，即使寻找最小值时，可以保证每次都取大小相同的数据中的前一个，交换操作也会改变数据的前后顺序，如给定数据 [5,2,5,1,2] ，第一次循环后得到 [1,2,5,5,2] ，5 的前后顺序已经改变

内存消耗：O(1) ，不需要任何额外空间，属于原地排序算法

执行效率：无论数据分布情况如何，时间复杂度都是 O(n^2) ，因为每次循环都需要遍历未排序区间寻找最小值，且循环完整执行 n 次

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {  // No need handle last element
        int minIdx = i;
        for (int j = i; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}