插入排序原理

插入排序(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)的时间，这对把一个基本有序的文件进行排序是一个简单而有效的方法。然而，对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。