排序---插入排序

插入排序

  每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧的数组依然有序。

  插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序，那么逆序较少，需要交换的次数也较少，时间复杂度就较低。

• 平均情况下插入排序需要约n * n/4次比较和约n * n/4次交换。
• 最坏的情况下需要约n * n/2次比较和约n * n/2次交换，最坏的情况就是数组逆序。
• 最好的情况下需要n-1次比较和0次交换，最好的情况就是数组有序。

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