概述

玩過(guò)撲克牌的同學(xué)都知道，把拿到的牌，和手上已有的牌比較，插入到合適的位置排好序，后面的牌位置就自動(dòng)后移一位。這個(gè)就是插入排序。

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:

時(shí)間復(fù)雜度

1. 最好的情況就是已經(jīng)排好序的數(shù)組，時(shí)間復(fù)雜度為O(n);
2. 最壞的情況就是逆序的，需要移動(dòng)1+2+3+...+n-1=n(n-1)/2，時(shí)間復(fù)雜度為O(n²);
3. 平均時(shí)間復(fù)雜度為O(n²) 。

空間復(fù)雜度

沒(méi)有分配額外空間，空間復(fù)雜度為O(1)。