时间空间复杂度分析--插入排序算法

时间空间复杂度分析–插入排序算法

大概说明

什么是插入排序算法？

冒泡排序算法就是从头指定某一个部分，用该部分的末尾的数依次和它前面的数进行比较，最后插入到合适的位置的算法。

循环往复，直到操作到0~ n。

代码部分

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {79,3213,3,5,45,65};
        insertSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
         }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
               swap(arr, j, j-1);
            }
        }
    }
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b]= temp;
    }
}

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

对它的时间复杂度分析&空间复杂度分析

先说时间复杂度：

他的时间复杂度是会根据数据的排列方式进行变换的，跟选择排序，冒泡排序有着本质的不同。

我们假设在最坏情况下，每次当前数都需要和前面所有数进行交换，那么就是 1 + 2 +。。。+n-1

是一个等差数列，所以时间复杂度是 O($n^2$)。这是最坏的情况。

而最好的情况就是，数组是排好序的，此时时间复杂度是O(n)。

最好的情况

再来说说空间复杂度

空间复杂度因为创建的变量就是temp所以空间复杂度为O(1).