惯例概念

有序度

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

满有序度

齐全有序的数组的有序度为满有序度,即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²)

抉择排序

三种排序比拟

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