IT虾米网

直接插入排序详解

admin 2018年05月26日 编程语言 141 0

基本思想

每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。

排序过程

1.初始化无序区、有序区,待排序数组的第一个元素为有序区,剩余元素为无序区;

2.遍历无序区,将无序区每一个元素插入到有序区的正确位置上;

Java算法实现

/** 
 * 排序接口类 
 * Created by zhouyh on 2018/5/25. 
 */ 
 public abstract class ISort { 
    public abstract int[] sort(int[] array); 
} 
 
/** 
 * 直接插入排序 
 * Created by zhouyh on 2018/5/25. 
 */ public class DirectInsertSort extends ISort { 
    @Override 
    public int[] sort(int[] array) { 
    int tmp; 
    for (int i=1; i<array.length; i++){ 
            tmp = array[i]; //array[i]的拷贝 
            //如果右侧无序区第一个元素
            array[i] < array[i-1]
            小于左侧有序区最后一个元素 
            //需要将左侧有序区比array[i]大的元素后移 
            if (array[i] < array[i-1]){ 
            int j = i-1; 
            while (j>=0 && tmp<array[j]){ 
                    array[j+1] = array[j]; 
                    j--; 
                } 
                array[j+1] = tmp; 
            } 
        } return array; 
    } 
}

 性能分析

时间复杂度,在比较的数组有序的情况下,为O(n),即此刻比较次数n-1次,移动次数0;在最坏的情况下,即数组逆序的情况下,为O(n^2),平均时间复杂度为O(n^2)

空间复杂度,直接排序的过程中,仅用到了一个临时变量,空间复杂端为O(1)

稳定性,直接插入排序为稳定排序,即排序前后的元素位置还是保持和排序前的前后顺序一致,例{2①,45,12,2④,3},排序后{2①,2④,3,12,45},其中两个2的前后顺序保持一致。

使用场景

在数组包含的元素数量较小情况下,可以选择插入排序,元素数量较大的情况下,不适用,因此时移动元素的次数较多;

在数组基本有序的情况下,适合使用插入排序,此时时间复杂度基本上为O(n)

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Spring知识总结详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。