插入排序

插入排序

时间复杂度为： O(n^2)

原理： 将数组分为两部分，将后部分元素逐一插入前部分有序元素的适当位置

思路： 插入排序的基本思想就是将无序序列插入到有序序列中，每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。

插入排序算法仍然需要O(N^2)的时间，但是在一般情况下，它要比冒泡排序快一倍，比选择排序还要快一点。

代码实现：

public class 插入排序 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int array[] = {9,1,5,3,7,8,2,6,4};
        chaRu(array);
    }

    public static void chaRu(int array[]) {
        int temp;
        System.out.println("插入排序：");
        for(int i=1;i<array.length;i++) {
            int j=i;
            temp = array[i];
            while( j>0 && temp < array[j-1]) {
                array[j] = array[j-1];
                j--;
            }
            array[j] = temp;
            System.out.print("第"+i+"次：");
            for(int k=0;k<array.length;k++) {
                System.out.print(array[k]+" ");
            }
            System.out.println();
        }
    }
}