内部排序算法：直接插入排序

基本思想

假設待排序的記錄存放在數組r[0..n-1]中。初始時，r[0]自成1個有序區，無序區為r[1..n-1]。 從i=1起直至i=n-1為止，依次将r[i]插入目前的有序區r[0..i-1]中，生成含n個記錄的有序區。

算法實作

直接插入排序算法，java實作，代碼如下所示：

<code>01</code>

<code>public</code> <code>abstract</code> <code>class</code> <code>sorter {</code>

<code>02</code>

<code></code><code>public</code> <code>abstract</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array);</code>

<code>03</code>

<code>}</code>

<code>04</code>

<code>05</code>

<code>public</code> <code>class</code> <code>straightinsertionsorter</code><code>extends</code> <code>sorter {</code>

<code>06</code>

<code>07</code>

<code></code><code>@override</code>

<code>08</code>

<code></code><code>public</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array) {</code>

<code>09</code>

<code></code><code>int</code> <code>tmp;</code>

<code>10</code>

<code></code><code>for</code> <code>(</code><code>int</code> <code>i =</code><code>1</code><code>; i &lt; array.length; i++) {</code>

<code>11</code>

<code></code><code>tmp = array[i];</code><code>// array[i]的拷貝</code>

<code>12</code>

<code></code><code>// 如果右側無序區第一個元素array[i] &lt; 左側有序區最大的array[i-1]，</code>

<code>13</code>

<code></code><code>// 需要将有序區比array[i]大的元素向後移動。</code>

<code>14</code>

<code></code><code>if</code> <code>(array[i] &lt; array[i -</code><code>1</code><code>]) {</code>

<code>15</code>

<code></code><code>int</code> <code>j = i -</code><code>1</code><code>;</code>

<code>16</code>

<code></code><code>while</code> <code>(j &gt;=</code><code>0</code> <code>&amp;&amp; tmp &lt; array[j]) {</code><code>// 從右到左掃描有序區</code>

<code>17</code>

<code></code><code>array[j +</code><code>1</code><code>] = array[j];</code><code>// 将左側有序區中元素比array[i]大的array[j+1]後移</code>

<code>18</code>

<code></code><code>j--;</code>

<code>19</code>

<code></code><code>}</code>

<code>20</code>

<code></code><code>// 如果array[i]&gt;=左側有序區最大的array[i-1]，或者經過掃描移動後，找到一個比array[i]小的元素</code>

<code>21</code>

<code></code><code>// 将右側無序區第一個元素tmp = array[i]放到正确的位置上</code>

<code>22</code>

<code></code><code>array[j +</code><code>1</code><code>] = tmp;</code>

<code>23</code>

<code>24</code>

<code>25</code>

<code>26</code>

直接插入排序算法，python實作，代碼如下所示：

<code>class</code> <code>sorter:</code>

<code></code><code>''</code><code>'</code>

<code></code><code>abstract sorter</code><code>class</code><code>, which provides shared methods being used by</code>

<code></code><code>subclasses.</code>

<code></code><code>__metaclass__ = abcmeta</code>

<code></code>

<code></code><code>@abstractmethod</code>

<code></code><code>def sort(self, array):</code>

<code></code><code>pass</code>

<code>class</code> <code>straightinsertionsorter(sorter):</code>

<code></code><code>straight insertion sorter</code>

<code></code><code>i =</code><code>0</code>

<code></code><code>length = len(array)</code>

<code></code><code>while</code> <code>i&lt;length -</code><code>1</code><code>:</code>

<code></code><code>k = i</code>

<code></code><code>j = i</code>

<code></code><code>while</code> <code>j&lt;length:</code>

<code></code><code>if</code> <code>array[j]&lt;array[k]:</code>

<code></code><code>k = j</code>

<code></code><code>j = j +</code><code>1</code>

<code></code><code>if</code> <code>k!=i:</code>

<code>27</code>

<code></code><code>array[k], array[i] = array[i], array[k]</code>

<code>28</code>

<code></code><code>i = i +</code><code>1</code>

排序過程

直接插入排序的執行過程，如下所示：

初始化無序區和有序區：數組第一個元素為有序區，其餘的元素作為無序區。

周遊無序區，将無序區的每一個元素插入到有序區正确的位置上。具體執行過程為：

每次取出無序區的第一個元素，如果該元素tmp大于有序區最後一個元素，不做任何操作；

如果tmp小于有序區最後一個元素，說明需要插入到有序區最後一個元素前面的某個位置，從後往前掃描有序區，如果有序區元素大于tmp，将有序區元素後移（第一次後移：tmp小于有序區最大的元素，有序區最大的元素後移覆寫無序區第一個元素，而無序區第一個元素的已經拷貝到tmp中；第二次後移：tmp小于有序區從後向前第二個的元素，有序區從後向前第二個元素後移覆寫有序區最大元素的位置，而有序區最後一個元素已經拷貝到無序區第一個元素的位置上；以此類推），直到找到一個元素比tmp小的元素（如果沒有找到，就插入到有序區首位置），有序區後移操作停止。

接着，将tmp插入到：從有序區由前至後找到的第一個比tmp小的元素的後面即可。此時，有序區增加一個元素，無序區減少一個元素，直到無序區元素個數為0，排序結束。

下面，通過執行個體來示範執行直接插入排序的過程，假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20，則執行排序過程如下所示：

初始有序區為{94}，無序區為{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。

對于array[1] = 12（無序區第一個元素）：臨時拷貝tmp = array[1] = 12，tmp = 12小于有序區{94}最後一個元素(94)，因為有序區隻有一個元素，是以将tmp插入到有序區首位置，此時，有序區為{12,94}，無序區為{34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。

對于array[2] = 34（無序區第一個元素）：臨時拷貝tmp = array[2] = 34，tmp = 34小于有序區{12,94}最後一個元素(94)，将94後移覆寫array[2]，亦即：array[2] = 94；繼續将tmp = 34與有序區{12,94}從後向前第二個元素比較，tmp = 34 &gt; 12，則直接将tmp = 34插入到12後面的位置。此時，有序區為{12,34,94}，無序區為{76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。

對于array[3] = 76（無序區第一個元素）：臨時拷貝tmp = array[3] = 76，tmp = 76小于有序區{12,34,94}最後一個元素(94)，将94後移覆寫array[3]，亦即：array[3] = 94；繼續将tmp = 76與有序區{12,34,94}從後向前第二個元素比較，tmp = 76 &gt; 34，則直接将tmp = 76插入到34後面的位置。此時，有序區為{12,34,76,94}，無序區為{26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。

……

依此類推執行，直到無序區沒有元素為止，則有序區即為排序後的數組。

算法分析

時間複雜度

最好情況：有序

通過直接插入排序的執行過程可以看到，如果待排序數組恰好為有序，則每次從大小為n-1的無序區數組取出一個元素，和有序區最後一個元素比較，一定是比最後一個元素大，需要插入到有序區最後一個元素的後面，也就是原地插入。

可見，比較次數為n-1次，數組元素移動次數為0次。

最壞情況：逆序

每次從無序區取出第一個元素，首先需要與有序區最後一個元素比較一次，然後繼續從有序區的最後一個元素比較，直到比較到有序區第一個元素，然後插入到有序區首位置。

每次從無序區取出第一個元素，移動放到拷貝tmp中，然後再将tmp與有序區元素比較，這個比較過程一共移動的次數為：有序區數組大小，最後還要将拷貝tmp移動插入到有序區的位置上。

在這個過程中：

有序區數組大小為1時，比較2次，移動3次；

有序區數組大小為2時，比較3次，移動4次；

有序區數組大小為n-1時，比較n次，移動n+1次。

可見：

比較的次數為：2+3+……+n = (n+2)(n-1)/2

移動的此時為：3+4+……+n+1 = (n+4)(n-1)/2

通過上面兩種情況的分析，直接插入排序的時間複雜度為o(n2)。

空間複雜度

在直接插入排序的過程中，隻用到一個tmp臨時存放待插入元素，是以空間複雜度為o(1)。

排序穩定性

通過上面的例子來看：

當有序區為{0,9,12,26,34,37,55,76,94}，無序區為{76,37,5,68,83,90,37,12,65,76,49}的時候，執行下一趟直接插入排序：

對于array[9] = 76（無序區第一個元素）：

臨時拷貝tmp = array[9] = 76，tmp = 76小于有序區{0,9,12,26,34,37,55,76,94}最後一個元素(94)，将94後移覆寫array[9]，亦即：array[9] = 94；繼續将tmp = 76與有序區{0,9,12,26,34,37,55,76,94}從後向前第二個元素(76)比較，tmp = 76 = 76，則直接将tmp = 76插入到有序區數組元素76後面的位置。此時，有序區為{0,9,12,26,34,37,55,76,76,94}，無序區為{37,5,68,83,90,37,12,65,76,49}。

繼續執行直至完成的過程中，對于兩個相等的數組元素，原始為排序數組中索引位置的大小關系并沒有發生改變，也就是說，對于值相等的元素e，存在ei1，ei2，……eik，其中i1，i2……ik是數組元素e在為排序數組中的索引位置，排序前有i1&lt;i2&lt;……&lt;ik，排序後仍然有j1&lt;j2&lt;……&lt;jk，其中j1&lt;j2&lt;……&lt;jk為排序後值相等的元素e的索引。

可見，直接插入排序是穩定的。