插入排序算法（java）

从索引为1的(第二个)位置开始插入。依次把后面的数插入到相应位置。摸牌一样。

比选择和冒泡排序在某些情况下要好一点（它俩严格就是O(n^2)）。数组本身就是有序的情况下。减少了比较的次数。

Java代码如下

 public static void insertSort(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }
        //从第二个位置开始，把当前位置的数和后面的数插入到相应的位置。
        for (int i = 1;i=0 && arr[j]>arr[j+1];j--){
                swap(arr,j,j+1);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }
    private static void swap1(int[] arr, int i,int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];//arr[j] = arr[i] ^ arr[j] ^ arr[j]  = arr[i];
        arr[i] = arr[i] ^ arr[j];//arr[i] = arr[i] ^ arr[j] ^ arr[i]  = arr[j];
    }