首页 > 代码库 > 【插入排序算法】初学算法之排序--直接插入排序
【插入排序算法】初学算法之排序--直接插入排序
前言：
厚厚一本《算法第四版》，看到五分之一就已经收益良多，而前五分之一又大部分是关于排序，有冒泡排序、快速排序、堆排序、直接插入排序、希尔排序等等，理解起来也不算特别的难，今天就跟大家分享其中的一种 —— 直接插入排序算法，这里我实现了javascript和java两个语言版本。
思路：
在生活中，如果我们要对扑克牌按大小排序，我们会怎么排呢？
① 首先找出一张牌 放在桌子上
② 拿出第二张牌，比第一张小就放上面，比第一张大就放下面
③ 拿出第三张牌，比第一张小就放上面，比第一张大就和第二张对比 ，比第二张小放上面，比第二长大再和下一张对比......
④ 重复步骤 最终扑克牌排序就完成了
从这三个步骤我们可以得出一些结论
① 放在桌子上的牌，总是有序的。
② 拿出的牌与前一张对比 直到遇到比那张小的 就放在上面
实现：
直接插入排序要点 ： 每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。
更清楚一点说： 将当前排序的数组元素，放到前面已经有序的元素的适当位置，循环到全部有序为止；
javascript实现：
function insertSort(arr){ for(var i = 1;i<arr.length;i++){ var temp = arr[i]; //待排序元素 var j = i; while(j>0){ if( temp < arr[j-1] ){ //如果前一个数比它自己大 var a = arr[j-1]; //交换它和它前一个元素 arr[j-1] = arr[j]; arr[j] = a; j--; //交换了j j的位置-- }else{ j=0; //当找到比它小的数 则结束这次排序 } } } return arr; }当输入 数组 [6,1,2,7,9,3,4,5,10,8,8,9] 时，得到的结果是 [1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10]
再分析一下while中的步骤:
function insertSort(arr){ //arr = [6,1,2,7,9,3,4,5,10,8,8,9] for(var i = 1;i<arr.length;i++){ var temp = arr[i]; // 例如i=1的话 temp = arr[1]; var j = i; while(j>0){ if( temp < arr[j-1] ){ // 1 < 6 等于 true var a = arr[j-1]; arr[j-1] = arr[j]; arr[j] = a; //交换1 - 6 j--; //i-- i=0 结束本次循环 这时候 arr = [1,6,2,7....] 再找到2 依次循环 }else{ j=0; } } } return arr; }java的实现：
public class SortUtil { //直接插入排序算法 public static void sort(Comparable[] a){ for(int i=1;i<a.length;i++){ Comparable tem = a[i]; //待排序元素 int j = i; while(j>0){ if(less(tem,a[j-1])){ //less比较元素 tem比前一个小的话 exch(a,j,j-1); j--; }else{ j=0; } } } } /* * compareTo 比较方法 * @param {Comparable} v 如果v小于w 返回true * @param {Comparable} w 如果v大于等于w 返回false * @return {boolean} 返回比较的值 * * */ public static boolean less(Comparable v,Comparable w){ return v.compareTo(w) < 0; } /* * compareTo 交换元素 * @param {Comparable[]} a 要交换的可排序数组 * @param {int} i 交换1下标 * @param {int} j 交换2下标 * * */ public static void exch(Comparable[] a,int i,int j){ Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void show(Comparable[] a){ for(int i=0;i<a.length;i++){ StdOut.print(a[i]+" "); StdOut.println(); } } /* * compareTo 测试元素是否有序 * @param {Comparable[]} a 可排序数组 * @return {boolean} 是否是有序数组 * * */ public static boolean isSorted(Comparable[] a){ for(int i=1;i<a.length;i++){ if(less(a[i],a[i-1])){ return false; } } return true; } /* * compareTo 将int[]转换成Integer[] * @param {int[]} a int数组 * @return {Integer[]} 转换后的Integer[] * * */ public static Integer[] intTo(int[] a){ Integer[] con = new Integer[a.length]; for(int i=0;i<a.length;i++){ con[i] = new Integer(a[i]); } return con; } //main public static void main(String[] args){ Integer[] a = intTo(In.readInts(args[0])); runTime runtime = new runTime(); sort(a); if(!isSorted(a)){StdOut.println("sort is error");System.exit(0);}; StdOut.println(runtime.End()); }}
总结：
① 抓住要点，每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。
② 学习时进行步骤分析，将数组按逻辑的方式人工排序一次，分析它的步骤，最终转化成代码实现
直接插入排序算法是希尔排序的基础方法，算法的大门前总有走不完的阶梯，只有坚持不懈、努力学习，才能登高而望，一览众山小。
【插入排序算法】初学算法之排序--直接插入排序