插入排序

?# 目標(biāo)：將數(shù)組從低到高（或從高到低）排序。

您將獲得一系列數(shù)字，需要按正確的順序排列。插入排序算法的工作原理如下：

把數(shù)字放在一堆。這堆是未分類的。

從堆中挑選一個(gè)數(shù)字。你選擇哪一個(gè)并不重要，但最容易從樁頂挑選。

將此數(shù)字插入新數(shù)組。

從未分類堆中選擇下一個(gè)數(shù)字，并將其插入到新數(shù)組中。它要么在您選擇的第一個(gè)數(shù)字之前或之后，所以現(xiàn)在這兩個(gè)數(shù)字被排序。

再次，從堆中選擇下一個(gè)數(shù)字，并將其插入到正確排序位置的數(shù)組中。

繼續(xù)這樣做，直到堆上沒(méi)有更多的數(shù)字。最終得到一個(gè)空堆和一個(gè)排序的數(shù)組。

這就是為什么這被稱為“插入”排序，因?yàn)槟銖亩阎腥∫粋€(gè)數(shù)字并將其插入數(shù)組中的正確排序位置。

一個(gè)例子

讓我們說(shuō)要排序的數(shù)字是[ 8, 3, 5, 4, 6 ]。這是我們未分類的堆。

選擇第一個(gè)數(shù)字，8然后將其插入新數(shù)組中。該陣列中還沒(méi)有任何東西，所以這很容易。排序的數(shù)組現(xiàn)在[ 8 ]和堆是[ 3, 5, 4, 6 ]。

從堆中選擇下一個(gè)數(shù)字3，然后將其插入到已排序的數(shù)組中。它應(yīng)該在之前8，因此排序的數(shù)組現(xiàn)在[ 3, 8 ]和堆減少到[ 5, 4, 6 ]。

從堆中選擇下一個(gè)數(shù)字5，然后將其插入到已排序的數(shù)組中。它介于3和之間8。排序的數(shù)組是[ 3, 5, 8 ]和堆[ 4, 6 ]。

重復(fù)此過(guò)程，直到堆積為空。

就地排序

上面的解釋使你看起來(lái)需要兩個(gè)數(shù)組：一個(gè)用于未分類的堆，另一個(gè)用于按排序順序包含數(shù)字。

但您可以就地執(zhí)行插入排序，而無(wú)需創(chuàng)建單獨(dú)的數(shù)組。您只需跟蹤數(shù)組的哪個(gè)部分已經(jīng)排序，哪個(gè)部分是未排序的堆。

最初，陣列是[ 8, 3, 5, 4, 6 ]。所述|欄示出了分選部分結(jié)束和樁開始：

這表明排序的部分是空的，樁開始于8。

處理完第一個(gè)號(hào)后，我們有：

分類的部分是[ 8 ]和樁[ 3, 5, 4, 6 ]。該|酒吧已經(jīng)轉(zhuǎn)向一個(gè)姿勢(shì)要正確。

這是排序期間數(shù)組內(nèi)容的變化方式：

在每個(gè)步驟中，|條形向上移動(dòng)一個(gè)位置。如您所見，數(shù)組的開頭|始終排序。堆縮小一，排序部分增加一，直到堆是空的，沒(méi)有更多未分類的數(shù)字。

如何插入

在每一步中，您從未分類堆中選擇最頂部的數(shù)字，并將其插入到數(shù)組的已排序部分。您必須將該數(shù)字放在適當(dāng)?shù)奈恢?，以便?shù)組的開頭保持排序。這是如何運(yùn)作的？

假設(shè)我們已經(jīng)完成了前幾個(gè)元素，并且數(shù)組看起來(lái)像這樣：

下一個(gè)要排序的數(shù)字是4。我們需要將其插入到[ 3, 5, 8 ]某處的已排序部分。

這是一種方法：查看前一個(gè)元素，8。

這大于4嗎？是的，所以4應(yīng)該在之前8。我們交換這兩個(gè)數(shù)字得到：

我們還沒(méi)有完成。新的前一個(gè)元素5也大于4。我們還交換了這兩個(gè)數(shù)字：

再看一下前面的元素。是3大于4？不它不是。這意味著我們完成了數(shù)字4。數(shù)組的開頭再次排序。

這是對(duì)插入排序算法的內(nèi)部循環(huán)的描述，您將在下一節(jié)中看到。它通過(guò)交換數(shù)字將數(shù)字從堆的頂部插入到已排序的部分。