JAVA插入排序

浏览数：28 / 时间：2015年06月08日

插入排序
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在实现上，通常采用in-place排序（原地排序,即只需用到O(1)的额外空间的排序），
因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

如有这么一个数列 int[] arrs=new int[]{1,3,4,5,2};
先取出2并临时存储,与它前一位对比
arrs[3]=5和2比较,5大于2,5后移到arrs[4],此时arrs[3]和arrs[4]都是5
从后往前移动到arrs[2]
arrs[2]=4和2比较,4大于2,4后移到arrs[3],此时arrs[2]和arrs[3]都是4
从后往前移动到arrs[1]
arrs[1]=3和2比较,3大于2,3后移到arrs[2],此时arrs[1]和arrs[2]都是3
从后往前移动到arrs[0]
arrs[0]=1和2比较,1小于2,所以2就放在arrs[0]的后面一位,arrs[1]上,arrs[1]=2(原先arrs[1]=3),完成排序

示意样图:

救命代码:

code

public class InsertSort {

    public static void main(String[] args) {

        int[] arrs = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        System.out.println("数组排序前");
        printArray(arrs);

        insertSort(arrs);

        System.out.println("数组排序后");
        printArray(arrs);

    }

    // 插入排序算法
    private static void insertSort(int[] arrs) {
        // TODO Auto-generated method stub
        for (int i = 0; i < arrs.length; i++) {
            // 先把元素的值临时存储起来,
            int temp = arrs[i];
            int j = i;
            while (j > 0 && arrs[j - 1] > temp) {
                // 把值后移,即把前面的值,赋值给它后面的位置,就好像是往后挪动一样,
                arrs[j] = arrs[j - 1];
                j--;
            }
            // 把临时取出来的值插入到最后一个挪动的元素的位置
            arrs[j] = temp;
        }
    }

    // 打印数组方法
    public static void printArray(int[] arrs) {
        System.out.print("[");
        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i]);
            if (i != arrs.length - 1) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }

}