iT邦幫忙

2017 iT 邦幫忙鐵人賽
DAY 9
0
自我挑戰組

C-Programming系列 第 9

C-Programming - Day09

插入排序法

插入排序法(Insertion Sort)是排序演算法的一種

他是一種簡單容易理解的排序演算法

其概念是利用另一個數列來存放已排序部分

逐一取出未排序數列中元素

從已排序數列由後往前找到適當的位置插入

建立一個新的陣列

一個一個元素去和陣列中比較

插入在正確的地方

插入排序法

然而實作上通常不使用額外的數列來儲存已排序的部分

而使用原地In-place的方式來完成

數列的左半部表示已排序部分

右半部表示未排序部分

不另外使用數列

在與已排序的部分比較時

利用指派(Assign)的方式將元素往右位移

來達到插入的效果

因為位移的關係需要有另一個變數來暫存最右邊的數值

實作插入排序法

分析

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

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

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

空間複雜度:O(1)

Stable sort:是


上一篇
C-Programming - Day08
系列文
C-Programming9
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言