算法與資料結構--插入排序

目錄

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;
    }