直接插入排序StraightInsertSort

1、算法思想

        将一個記錄插入到已排序好的有序表中，進而得到一個新的記錄數增1的有序表。

        即：先将序列的第1個記錄看成是一個有序的子序列，然後從第2個記錄逐個進行插入，直至整個序列有序為止。

要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。

2、代碼實作

3、算法分析

      如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。是以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，是以插入排序是

穩定

的。

      如果目标是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況如下。

最好情況：序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。

最壞情況：序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次（計算式為1+2+……+

n-1）。

直接插入排序屬于穩定的排序，最壞時間複雜度為o(n^2)，最好時間複雜度為o(n)，空間複雜度為o(1)。

插入排序的指派操作是比較操作的次數加上(n-1)次。

是以，插入排序不适合對于資料量比較大的排序應用。