插入排序

1. 前言

本節(jié)內(nèi)容是排序算法系列之一：插入排序，主要講解了插入排序的主體思路，選取了一個(gè)待排序的數(shù)字列表對(duì)插入排序算法進(jìn)行了演示，給出了插入排序算法的 Java 代碼實(shí)現(xiàn)，幫助大家可以更好地理解插入排序算法。

2. 什么是插入排序？

插入排序（Insert Sort），是計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域中較為簡(jiǎn)單的一種排序算法。

顧名思義，插入排序是通過(guò)不斷插入待排序的元素完成整個(gè)排序過(guò)程。插入排序是一種很簡(jiǎn)單的排序方式，基本思想就是將一個(gè)元素插入到已經(jīng)排序好的序列中，從而形成一個(gè)新的有序序列。它重復(fù)地選擇未排序的元素，將其插入已經(jīng)排序好的序列中，直到?jīng)]有待排序元素時(shí)，整個(gè)排序過(guò)程完成。

插入排序的工作方式就像大家打撲克牌時(shí)抓牌一樣。開(kāi)始時(shí)，我們手上是沒(méi)有牌的，依次從桌面上面抓取撲克牌，然后插入自己手中已有撲克牌的位置中，只是插入的時(shí)候我們按照一定的順序?qū)⑺迦氲胶线m的位置中。

3. 插入排序過(guò)程

在介紹完插入排序之后，我們一起來(lái)看一下插入排序的實(shí)現(xiàn)步驟具體是什么樣的吧。同樣的，和之前介紹冒泡排序時(shí)一樣，這里我們假設(shè)待排序的序列為 [9,2,11,7,12,5] ，我們按照從小到大的序列進(jìn)行排序。

3.1 算法步驟

1. 步驟 1：

選擇待排序序列中的第一個(gè)元素作為一個(gè)有序序列，將剩余元素看成是一個(gè)未排序序列；

2. 步驟 2：

依次從未排序序列中選擇一個(gè)元素，與已排序序列中的元素依次比較，將其插入到合適的位置。

其實(shí)，上面的步驟 2 每執(zhí)行一次，都會(huì)有一個(gè)新的排序好的序列形成，并且這個(gè)新的排序好的序列在依次變大，直至整個(gè)排序工作完成。接下來(lái)，讓我們用上面的待排序數(shù)字序列 [9,2,11,7,12,5] 進(jìn)行整個(gè)算法步驟的排序演示工作。

3.2 算法演示

按照 2.1 節(jié)的排序步驟，首先我們會(huì)選擇出待排序隊(duì)列中的第一個(gè)元素作為一個(gè)已經(jīng)排序好的序列，將剩余元素作為一個(gè)未排序好的序列。所以開(kāi)始我們將待排序序列 [9,2,11,7,12,5] 分成了排序好的序列 [9] 和未排序序列 [2,11,7,12,5]，如下：

[9,2,11,7,12,5]  --> [9];[2,11,7,12,5]   //[9]排序好的序列，[2,11,7,12,5]未排序序列，中間用;分開(kāi)

接著，我們調(diào)用 2.1 中的步驟 2，依次從未排序序列中選擇一個(gè)元素，與已排序序列中的元素依次比較，將其插入到合適的位置。整個(gè)過(guò)程如下：

[9];[2,11,7,12,5]   -->  [2,9];[11,7,12,5]	 //選擇未排序元素2，插入排序好的序列[9]形成新的排序好序列[2,9]
[2,9];[11,7,12,5]   -->  [2,9,11];[7,12,5]	 //選擇未排序元素11，插入排序好的序列[2,9]形成新的排序好序列[2,9,11]
[2,9,11];[7,12,5]   -->  [2,7,9,11];[12,5]	 //選擇未排序元素7，插入排序好的序列[2,9,11]形成新的排序好序列[2,7,9,11]
[2,7,9,11];[12,5]   -->  [2,7,9,11,12];[5]	 //選擇未排序元素12，插入排序好的序列[2,7,9,11]形成新的排序好序列[2,7,9,11,12]
[2,7,9,11,12];[5]   -->  [2,5,7,9,11,12];[]	 //選擇未排序元素5，插入排序好的序列[2,7,9,11,12]形成新的排序好序列[2,5,7,9,11,12]

步驟 2 會(huì)依次從未排序序列中選擇一個(gè)元素，按照如上過(guò)程一樣，將待排序元素插入到已經(jīng)排序好的序列中，形成一個(gè)新的排序好的序列，減少待排序元素的數(shù)量，直至整個(gè)排序工作完成。

Tips: 步驟 2 每次執(zhí)行的時(shí)候，都是需要將待排序元素與已經(jīng)排序好的序列中的每個(gè)元素進(jìn)行依次比較，才能找到待排序元素的插入位置。例如：[2,9,11] ; [7,12,5] --> [2,7,9,11] ; [12,5]，在將待排序元素 7 插入到排序好的序列 [2,9,11] 中時(shí)，需要依次將 7 和序列 [2,9,11] 中的元素比較，發(fā)現(xiàn) 7>2，繼續(xù)比較下一個(gè)，7<9，所以 7 應(yīng)該插入到排序好的序列 [2,9,11] 的 2 和 9 之間。

從上面的示例可以看出，其實(shí)整個(gè)插入排序的過(guò)程，會(huì)將原來(lái)的待排序序列分成已經(jīng)排序好的序列和尚未排序的序列，從尚未排序的序列中依次選擇元素，插入到排序好的序列中。

4. Java 代碼實(shí)現(xiàn)

在說(shuō)明插入排序的整個(gè)過(guò)程之后，接下來(lái)，我們看看如何用 Java 代碼實(shí)現(xiàn)插入排序算法。

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        //初始化需要排序的數(shù)組
        int array[] = {9, 2, 11, 7, 12, 5};

        //初始化一個(gè)與待排序數(shù)組大小相同的數(shù)組，用來(lái)存放排序好的序列
        int sortArray[] = new int[array.length];

        //步驟1：待排序數(shù)組中選擇第一個(gè)元素作為已經(jīng)排序好的元素（數(shù)組的下標(biāo)0表示第一個(gè)元素）
        sortArray[0] = array[0];

        //步驟2：依次遍歷未排序的元素，將其插入已排序序列中
        for (int i = 1; i < array.length; i++) {
            //待排序元素
            int temp = array[i];
            //記錄待排序元素需要插入已排序數(shù)組中的位置
            int index = i;
            //從已排序好的數(shù)組右邊依次遍歷數(shù)組，直到找到待排序元素需要插入的位置
            while(  index > 0  && temp < sortArray[index-1] ){
                sortArray[index] = sortArray[index-1];
                index--;
            }
            //插入待排序元素
            sortArray[index] = temp;
        }

        //打印出排序好的序列
        System.out.println(Arrays.toString(sortArray));
    }

}

運(yùn)行結(jié)果如下：

[2, 5, 7, 9, 11, 12]

代碼中的第 7 行初始化一個(gè)需要排序的數(shù)組，第 10 行初始化一個(gè)與待排序數(shù)組大小相同的數(shù)組，用來(lái)存放排序好的序列。第 13 行將待排序數(shù)組中選擇第一個(gè)元素作為已經(jīng)排序好的元素，放入排序好的數(shù)組中。第 16 行是外層循環(huán)，不斷地重復(fù)排序工作，將未排序的元素插入到排序好的序列中。第 22 行是內(nèi)部的 while 循環(huán)，找到待排序元素需要插入的排序好的數(shù)組中的位置，實(shí)現(xiàn)插入排序。第 31 行打印出排序好的數(shù)組。

5. 小結(jié)

本節(jié)主要學(xué)習(xí)了插入排序算法，本節(jié)內(nèi)容需要熟悉插入排序的算法流程，知道插入排序算法的實(shí)現(xiàn)思路，可以自己用代碼實(shí)現(xiàn)插入排序算法。在學(xué)完本節(jié)課程之后，我們已經(jīng)完成了排序算法中的冒泡排序、插入排序的學(xué)習(xí)。