算法与数据结构--插入排序

59 阅读 0 评论 39 点赞

我是靠谱客的博主爱听歌裙子，最近开发中收集的这篇文章主要介绍算法与数据结构--插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、插入排序的原理

2、过程分析

3、参考代码

1、插入排序的原理

将数组分为两部分, 将后边部分的第一个逐一与前部分每一个元素比较，在合理位置插入
插入排序算法效率要高于选择排序和冒泡排序

插入排序丼例：{8 , 2 , 3 , 7 , 1}的排序过程如下所示：

第1步，假设第一个元素是已排序的 {8|2,3,7,1}

第2步，用2和"|"之前的所有元素比较，并插入 {8|2,3,7,1}

取出2（temp=2）

temp和8比，比8小，将2的位置赋值为大数（array[1]=8） {8|8,3,7,1}

因为已到边界，直接赋值（array[0]=2） {2,8|3,7,1}

2和8排序完成

第3步，用3和"|"之前的所有元素比较，并插入 {2,8|3,7,1}

取出3（temp=3）

temp和8比，比8小，3的位置赋值给大数（array[2]=8） {2,8|8,7,1}

temp和2比，比2大，插入2后面（array[1]=3） {2,3,8|7,1}

3、2、8排序完成

第4步，用7和"|"之前的所以元素比较，并插入 {2,3,8|7,1}

取出7（temp=7）

temp和8比，比8小，7的位置赋值给大数（array[3]=8） {2,3,8|8,1}

temp和3比，比3大，插入3后面（array[2]=7） {2,3,7,8|1}

7、2、3、8排序完成

第5步，用1和"|"之前的所以元素比较，幵插入 {2,3,7,8|1}

取出1（temp=1）

temp和8比，比8小，1的位置赋值给大数8 {2,3,7,8|8}

temp和7比，比7小，8的位置赋值给大数7 {2,3,7,7|8}

temp和3比，比3小，7的位置赋值给大数3 {2,3,3,7|8}

temp和2比，比2小，3的位置赋值给大数2 {2,2,3,7|8}

到边界，赋值（array[0]=1） {1,2,3,7,8|}

1、2、3、7、8排序完成

2、过程分析

temp 代表取出待插入的元素
i 代表后组待插入元素的位置
j 代表前组每个元素的位置

array	i	temp	j	array[j]	temp < array[j]	[j]交换[j + 1]	temp插入[j+1]
第1轮
{8\|2,3,7,1}	[1]	2	[0]	8	TRUE	8->[1]	2->[0]
{2,8\|3,7,1}
第2轮
{2,8\|3,7,1}	[2]	3	[1]	8	TRUE	8->[2]	3->[1]
{2,3\|8,7,1}	[2]	3	[0]	2	FALSE	--	--
{2,3,8\|7,1}
第3轮
{2,3,8\|7,1}	[3]	7	[2]	8	TRUE	8->[3]	3->[2]
{2,3,7\|8,1}	[3]	7	[1]	3	FALSE	--	--
{2,3,7,8\|1}
第4轮
{2,3,7,8\|1}	[4]	1	[3]	8	TRUE	8->[4]	1->[3]
{2,3,7,1\|8}	[4]	1	[2]	7	TRUE	7->[3]	1->[2]
{2,3,1,7\|8}	[4]	1	[1]	3	TRUE	3->[2]	1->[1]
{2,1,3,7\|8}	[4]	1	[0]	2	TRUE	2->[1]	1->[0]
{1,2,3,7\|8}
结果
{1,2,3,7,8}

i 的取值范围是： i=1 ~ <array.length i++
j 的取值范围是： j= i-1 ~ >=0 j--
伪代码如下：

    temp = [i]; 
    if(temp<[j]){ 
        [j]->[j+1] //移动 
    }else{ 
        break j; 
    } 
    temp->[j+1]; //插入

3、参考代码

    public static void main(String[] args) {
        int[] array = {8, 2, 3, 7, 1};
        System.out.println(Arrays.toString(insertSort(array)));
    }

    private static int[] insertSort(int[] array) {
        int i, j, temp;
        for (i = 1; i < array.length; i++) {
            temp = array[i];
            for (j = i - 1; j >= 0; j--) {
                if (temp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
        return array;
    }