插入排序

声明： 主要代码和部分算法说明参考自算法(第四版)，这里将代码列出，是想和大家交流一些学习心得。

1.准备

为了让把精力放在算法的实现上，所以需要做一些准备工作，书写一些模板代码，这些代码。

import edu.princeton.cs.algs4.In; import edu.princeton.cs.algs4.StdOut; //p153 排序算法类的模板 public class Example { //对数组中的元素(实现了Comparable接口)进行排序 public static void sort(Comparable[] a){ // //选择排序 // Selection.sort(a); //插入排序 Insertion.sort(a); } //判断v是否小于w public static boolean less(Comparable v,Comparable w){ //如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数 return v.compareTo(w) < 0; } //交换两个元素的位置 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(); } //判断数组a是否有序 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; } //测试 public static void main(String[] args) { @SuppressWarnings("deprecation") String[] a = In.readStrings(); sort(a); if(isSorted(a)) System.out.println("有序"); show(a); } }

插入排序算法：

//157 插入排序 public class Insertion { //升序排序 public static void sort(Comparable[] a) { int N = a.length; //数组长度 //外层for循环作用：N个数，需要拿出N-1个数进行插入，从第二个数-最后一个数 for(int i=1; i<N; i++) //内层for循环用于将当前元素插入到前面的有序集合中 for(int j=i; j>0 && Example.less(a[j], a[j-1]); j--) Example.exch(a, j, j-1); } }

插入排序的核心思想是： 当i=1时，将a[1]插入到已经排好序的集合{ a[0] }中。 当i=2时，将a[2]插入到已经排好序的集合{ a[0] a[1] }中。 依次类推，直至整个数组排好序。

2.测试

以文件：tiny.txt 作为输入参数 排序前：S O R T E X A M P L E 排序后：A E E L M O P R S T X

3.总结

插入排序的不足： 对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。 而希尔排序就可以很好的改良这个问题。 http://blog.csdn.net/qq_32293345/article/details/78898787