插入排序

插入排序

概述

插入排序所需的时间与数组的初始顺序有关,对于已经有序或部分有序的数组进行排序时有优势

实现

    /**
     * 插入排序
     * 思路: 将一个元素插入到已经有序的序列中;
     * 步骤: 1.起始时假设数组中索引 [0] 的为有序序列,此时将[1]插入,结果索引[0],[1]为有序序列
     *   　　2.继续索引[0],[1]为有序序列,将[2]插入,结果[0],[1],[2]为有序序列
     *　　　 3.依次类推,将[3]...插入,最后执行到数组末尾,则所有元素都插入到有序序列中去,排序完成
     */
    public void insertion(int[] arr){
        for(int i=1,len=arr.length;i<len;++i){
            for(int j=i;j>0 && arr[j]<arr[j-1];j--){
                //交换
                arr[j] = arr[j]^arr[j-1];
                arr[j-1] = arr[j]^arr[j-1];
                arr[j] = arr[j]^arr[j-1];
            }
        }
    }