插入排序

概述

玩过扑克牌的同学都知道，把拿到的牌，和手上已有的牌比较，插入到合适的位置排好序，后面的牌位置就自动后移一位。这个就是插入排序。

java代码

public class InsertSort {
    public static void main(String[] args) {
        int[] array = {32,5,66,48,99,21,55};
        System.out.print("InsertSort\n");
        printArray(array);
        System.out.print("start:\n");
        insertSort(array);
        System.out.print("end:\n");
    }

    static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int temp = arr[i];
            for(int j=i-1;j>=0;j--){
                if(temp<arr[j]){
                    arr[j+1]=arr[j];//后移
                    arr[j] = temp;
                }else{
                    arr[j+1] = temp;
                    break;
                }
            }
            printArray(arr);
        }
    }


    static void printArray(int[] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print("\n");
    }
}

输出

InsertSort
32 5 66 48 99 21 55 
start:
5 32 66 48 99 21 55 
5 32 66 48 99 21 55 
5 32 48 66 99 21 55 
5 32 48 66 99 21 55 
5 21 32 48 66 99 55 
5 21 32 48 55 66 99 
end:

时间复杂度

1. 最好的情况就是已经排好序的数组，时间复杂度为O(n);
2. 最坏的情况就是逆序的，需要移动1+2+3+...+n-1=n(n-1)/2，时间复杂度为O(n²);
3. 平均时间复杂度为O(n²) 。

空间复杂度

没有分配额外空间，空间复杂度为O(1)。