排序算法-直接插入排序

直接插入排序

思想：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

        算法复杂度：如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。

最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。

最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。

       插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n²)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

package com.liuhao;

public class InsertionSort {

    /**
     *  直接插入排序
     *  基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，
     *  现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，
     *  直到全部排好顺序。
     * @param a
     * @return
     */
    public int[] insertSort(int a[]){
       
        int temp = 0;
       
        for(int i=1; i<a.length; i++){
            int j = i-1;
            temp = a[i];
           
            for(;j>=0 && a[j]>temp; j--){
                a[j+1] = a[j];
            }
           
            a[j+1] = temp;
        }
       
        return a;
    }
}