插入排序

数组【3】【2】【3】【1】【4】

下标 【0】【1】【2】【3】【4】

原理

1.0~0位置有序

2.0~1位置有序，不有序就交换

3.0~2位置有序，不有序就交换

4.0~3位置有序…

N. 0~N-1位置有序….

这就是插入排序的原理。

时间复杂度是多少？

数据状况会影响时间复杂度，应该用最差的数据状况来估计时间复杂度，所以插入排序的时间复杂度还是O（N*N），

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Code02_insertionSort {
    public static void insertionSort(int[] arr){
        if(arr == null || arr.length<2){
            return;
        }
        for(int i = 1;i<arr.length;i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j +1);
            }
        }
    }
    //使用异或交换比赋值效率低，不能交换float数据，但是解决了数据溢出的风险（当数据特别大的时候用）
    public static void swap(int[] arr,int i ,int j){
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        int[] arr={12,45,4,5456,12,12};
        insertionSort(arr);
        for(int i= 0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
}