插入排序

插入排序算法的运作如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素与新元素交换
4. 重复步骤3，直到交换到已排序的元素小于或者等于新元素的位置
5. 重复2~4步骤

选择排序复杂度分析

时间复杂度O(N^2)，额外的空间复杂度O(1)

最坏时间复杂度O(N^2)，最优时间复杂度O(n)

源码

public class 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);
            }
        }
    }
    
    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];
    }
}