排序算法之直接插入排序

定义：将一个待排序的记录，插入到已经排好序的元素序列中去，直到所有的元素都插入到以排好序的元素序列中，则排序完成。
思路：
①.将序列分为有序和待排序序列，第一步，第1个元素为有序序列，其它为无序序列；
②.将第2个元素，与第1个元素比较，若较大，则第1个元素后移一位，第2个元素放在第一位；否则，保持不变；至此，有序序列中元素个数为2；
③.将第n个元素，依次与前n-1个有序元素比较，若较大，则被比较元素后移一位；否则，比较结束，将待插入元素插入到被比较元素后一位；
④.重复以上步骤，直至所有元素插入完成。
图解：
排序算法之直接插入排序
总结：直接插入排序是一种比较简单，易于理解的排序算法，有点类似打扑克牌摸牌，当然，如果牌不按大小整理则另当别论。直接插入排序，比较次数较少；但是执行插入的时候，元素向后移动的次数多，当然，如果元素使用链表的形式存储，则不会存在此问题。
代码实现：

/**
 * 直接插入排序
 * @param arr
 * @return
 */
public static void insertSort(int []arr){
    // 获取数组长度
    int len=arr.length;
    for(int i=1;i<len;i++){//因为第一次不用，所以从1开始
        // 待插入的数
        int insertNum=arr[i];
        //将要插入的元素，与已经排好序的序列中的每一个元素进行比较，j为待比较的索引
        int j=i-1;
        // 若未比较完，且该数大于待排序树，则被比较的数后移一位
        while(j>=0 && arr[j]>insertNum){
            // 后移一位
            arr[j+1]=arr[j];
            // 索引-1，再与前一个数进行比较
            j--;
        }
        // 比较完成，将元素插入到j索引后一位
        arr[j+1] = insertNum;
    }
}

排序算法之直接插入排序

相关推荐