算法学习笔记--插入排序

插入排序：将每一个元素插入到其他已经有序的数组的适当位置。为了给插入的元素腾出空间，需要将其余所有元素在插入之前都向右移动一位。

插入排序也很简单，java代码如下:

/**
 *插入排序
 */
public class Insertion {

    public static void sort(int[] a){

        int N = a.length;
        for (int i = 1; i < N; i++) {     //将a[i]插入到a[i-1],a[i-2],a[i-3]...之中
            for (int j = i; j > 0 && (a[j] < a[j-1]); j--) {
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }
}

插入排序轨迹图：

插入排序的特点：

1、对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要~（N^2）/4次比较以及~（N^2）/4次交换。最坏的情况下需要（N^2）/2次比较和（N^2）/2次交换，最好的情况下需要N-1次比较和0次交换。

2、插入排序对于部分有序的数组十分高效，也适合小规模数组。

以下几种场景适合插入排序：

1、数组中每个元素距离它的最终位置都不远。

2、一个有序的大数组接一个小数组

3、数组中只有几个元素的位置不正确。

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/yaoliao_11/article/details/53494792
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-06-27 23:10:31
阅读 ( 1008 )
分类：算法

算法学习笔记--插入排序

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看