`

排序算法-直接插入排序

阅读更多

直接插入排序

思想:

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

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
        算法复杂度:如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。
最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。
最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。
       插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
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;
    }
}

 

 
0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics