惯例概念

有序度

有序度是数组中具备有序关系的元素对的个数

满有序度

齐全有序的数组的有序度为满有序度, 即 n 长度的数组满有序度为 Cn² , 即 n *(n-1)/2;

逆序度

满有序度 - 有序度 = 逆序度

冒泡排序

public class SortMain {public static void main(String[] args) {int[] arr = {4, 5, 6, 3, 2, 1};
        // 有序度为 3 , 满序度为 C52 5*6/2=15 , 逆序度为 12
        int count = 0;
        count = bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("排序执行:" + count);
    }

    public static int bubbleSort(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            // 当一次冒泡中不再替换数据, 则示意齐全有序, 可随时退出循环
            boolean flag = false;
            for (int j = 1; j < arr.length - i; j++) {
                // 比拟 j 与 i
                if (arr[j - 1] > arr[j]) {
                    count++;
                    swap(arr, j);
                    flag = true;
                }
            }
            if (!flag) {break;}
        }
        return count;
    }

    private static void swap(int[] arr, int j) {int temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
    }
}

冒泡排序的特点:

• 原地排序, 空间复杂度为 O(1)
• 稳固排序, 相邻且相等的元素不做替换, 确保两个元素排序后与排序前的绝对程序统一
• 工夫复杂度 最好状况为 O(n), 最差状况为 O(n²) , 即 n *(n-1)/2
• 替换次数等于逆序度

插入排序

public static int insertSort(int[] arr) {
        int count = 0;// 每挪动一次加一
        for (int i = 1; i < arr.length; i++) {int temp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {if (temp < arr[j]) {
                    count++;
                    arr[j + 1] = arr[j];
                } else {break;}
            }
            arr[j + 1] = temp;
        }
        return count;
    }

插入排序的特点:

• 原地排序, 空间复杂度为 O(1)
• 稳固的排序算法
• 工夫复杂度 O(n²)

抉择排序

三种排序比拟

• 抉择排序不是稳固排序, 稍弱于冒泡与插入排序
• 冒泡排序在替换时须要三个赋值操作, 插入排序只有一个
• 插入排序效率略高于冒泡排序