一、插入排序

思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。

关键问题：在前面已经排好序的序列中找到合适的插入位置。

方法：直接插入排序、二分插入排序、希尔排序

二、直接插入排序

基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

java实现

public class ZhiJieChaRu {    /**     * 直接插入排序第一版     * @param a     * @return     */    public static int[] sort1(int[] a) {        //假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次         //这里可以直接i=1从第二位开始处理也一样        for(int i=1;i<a.length;i++) {            //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置            for(int j=i-1;j>=0;j--) {                //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置                if(a[j+1]>a[j]) {                    break;                }else {                        //这种每次比较后都马上移动，每次都定义临时变量，我们其实可以找到位置，最后再出入一次即可                        int temp = a[j+1];                        a[j+1]=a[j];                        a[j]=temp;                    }                }            }            return a;    }    /**     * 插入排序改进版，找到位置最后才插入     * @param a     * @return     */    public static int[] sort2(int[] a) {        //假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次         //这里可以直接i=1从第二位开始处理也一样        for(int i=1;i<a.length;i++) {            //缓存待排序的记录            int temp = a[i];            int j;//这个是待插入的位置-1            //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置            for(j=i-1;j>=0;j--) {                //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置                if(temp>a[j]) {                    break;                }else {                    //把当前记录往后面移动一位                    a[j+1]=a[j];                }            }            a[j+1]=temp;        }            return a;    }    public static void main(String[] args) {        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};        System.out.print("排序之前：");        for (int i = 0; i < a.length; i++) {            System.out.print(a[i]+" ");        }        System.out.println();        System.out.print("sort1：");        int[] a1 = sort1(a);        int[] a2 = sort2(a);        for (int i = 0; i < a1.length; i++) {            System.out.print(a1[i]+" ");        }        System.out.println();        System.out.print("sort2：");        for (int i = 0; i < a2.length; i++) {            System.out.print(a2[i]+" ");        }    }}

上面有两种实现方法，第二种sort2比较好，不用每次都新建temp;