概述
玩過撲克牌的同學都知道盒发，把拿到的牌橄碾，和手上已有的牌比較，插入到合適的位置排好序级及，后面的牌位置就自動后移一位乒疏。這個就是插入排序。
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:
時間復雜度
- 最好的情況就是已經排好序的數組饮焦，時間復雜度為O(n);
- 最壞的情況就是逆序的怕吴，需要移動1+2+3+...+n-1=n(n-1)/2窍侧，時間復雜度為O(n2);
- 平均時間復雜度為O(n2) 。
空間復雜度
沒有分配額外空間转绷，空間復雜度為O(1)伟件。
