首页 > 代码库 > 插入排序

插入排序

package foo;import java.util.Arrays;public class Main {        public static void insertionSort(int[] a, int len) {        int in, out;        int temp;        for (out=1;out<len;++out) {            temp = a[out];            in = out;            while (in>0&&a[in-1]>temp) {                a[in] = a[in-1];                --in;            }            a[in] = temp;        }    }        public static void main(String[] args) throws Exception {        int[] a = new int[]{3,2,1,5,4};        insertionSort(a, a.length);        System.out.println(Arrays.toString(a));    }}

插入排序的效率:O(N*N), 比较N*N/4,复制N*N/4,插入排序在随机数的情况下,比冒泡快一倍,比选择稍快,在基本有序的数组中,插入排序几乎只需要O(N),在逆序的情况下,并不比冒泡快。