插入排序原理

插入排序(InsertionSort)，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

插入排序示意图

插入排序java代码

class ArrayInsert {    private long[] a;    private int nElems;    public ArrayInsert(int max) {        a = new long[max];        nElems = 0;    }    public void insert(long value) {        a[nElems] = value;        nElems++;    }    public void display() {        for (int j = 0; j < nElems; j++) {            System.out.print(a[j] + " ");        }        System.out.println(" ");    }    public void insertionSort() { //插入排序核心        int in, out;        for (out = 1; out < nElems; out++) { //out is dividing line            long temp = a[out]; //remove marked item            in = out; //start shifts at out            while (in > 0 && a[in - 1] >= temp) { //unil one is smaller                a[in] = a[in - 1]; //shift item to right                --in; //go left one position            }            a[in] = temp; //insert marked item        }    }}public class inserSort {    /**     * @param args     */    public static void main(String[] args) {// TODO Auto-generated method stub        int maxSize = 100;        ArrayInsert arr;        arr = new ArrayInsert(maxSize);        arr.insert(77);        arr.insert(99);        arr.insert(44);        arr.insert(55);        arr.insert(22);        arr.insert(88);        arr.insert(11);        arr.insert(00);        arr.insert(66);        arr.insert(33);        System.out.println("before insertionsort");        arr.display();        arr.insertionSort();        System.out.println("after insertionsort");        arr.display();    }}

插入排序比冒泡排序快一倍，比选择排序略快。在任意情况下，和其他的排序例程一样，对于随机顺序的数据进行插入排序也需要O(n^2)的时间级。对于已经有序或基本有序的数据来说，插入排序要好得多。当数据有序的时候，while循环的条件总是假，所以它变成了外循环中的一个简单语句，执行N-1次。在这种情况下，算法运行只需要O(N)的时问。如果数据基本有序，插入排序几乎只需要O(N)的时间，这对把一个基本有序的文件进行排序是一个简单而有效的方法。然而，对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。