計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫

插入排序法(Insertion Sort)是排序演算法的一種，他是一種簡單容易理解的排序演算法，其概念是利用另一個數列來存放已排序部分，逐一取出未排序數列中元素，從已排序數列由後往前找到適當的位置插入。運算流程如下：

從未排序數列取出一元素。由後往前和已排序數列元素比較，直到遇到不大於自己的元素並插入此元素之後；若都沒有則插入在最前面。重複以上動作直到未排序數列全部處理完成。

流程示意圖：

    

然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地(In-place)的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。在與已排序的部分比較時，利用指派(Assign)的方式將元素往右位移，來達...

查看完整內容

插入排序法(Insertion Sort)是排序演算法的一種，他是一種簡單容易理解的排序演算法，其概念是利用另一個數列來存放已排序部分，逐一取出未排序數列中元素，從已排序數列由後往前找到適當的位置插入。運算流程如下：

1. 從未排序數列取出一元素。
2. 由後往前和已排序數列元素比較，直到遇到不大於自己的元素並插入此元素之後；若都沒有則插入在最前面。
3. 重複以上動作直到未排序數列全部處理完成。

流程示意圖：

    

然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地(In-place)的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。在與已排序的部分比較時，利用指派(Assign)的方式將元素往右位移，來達到插入的效果，因為位移的關係需要有另一個變數來暫存最右邊的數值。運算流程如下：

1. 將未排序的部分最左邊元素儲存到暫存變數。
2. 由後往前和已排序部分元素比較，若比自己大則將該元素往右邊位移。
3. 重複2的動作直到遇到不大於自己的元素，將暫存變數寫入在該元素之後；若都沒有則寫入在最前面。
4. 重複以上動作直到未排序部分全部處理完成。

流程示意圖：

  

分析

最佳時間複雜度：O(n)

平均時間複雜度：O(n^2)

最差時間複雜度：O(n^2)

空間複雜度：O(1)

Stable sort：是