各個Sorting algorithm的複雜度:

Insertion Sort:
從 i=1 做到 i=n-1,每一round拿現在這個數與前面的數相比,若數字比前面的小,則將前面的數往後移,直到找到比它小的數,在插入比它小的數字的下一個位置。由於此方法從左邊開始,然後每一次數字的左邊一定是個被sort好的subarray,所以此方法不怕插入到不對的位置。

Selection Sort:
從 i=0 做到 i=n-1,每一round從當個位置右邊的subarray中找出最小的數字,找到後與他交換位置。

Bubble Sort:
做size-1次,每一次選擇0~size-1的範圍,結束後將範圍縮小一。每一次都兩兩交換數,直到把最大換到範圍的最末端。

Quick Sort:
Quick sort每回合利用一個數作為pivot,將front and end之間做partition。通常以最後一個數作為pivot,回合開始時,設定兩個位置,left_end(圖中是i) and right_end(圖中),為的就是指出left part and right part的尾端,然後開始由左至右每個right_end指向的數與pivot比大小,若發現數字比pivot小,則代表right_end指向的數應被加入left part,所以會先將left_end+1(空出個位子給left part),再將目前right_end指向的數與left_end做交換,這樣做直到right_end到達pivot的前一個位置結束。當partition做完後,再將pivot與right part的第一個位置做交換,來將pivot擺到left part and right part之間。接著用recursion 持兩邊都做直到無法partition。

C code solution:

Merge Sort:
採取Divide and Conquer的方式。首先有個主function merge_sort和一個副function Merge,merge_sort裡面主導主要流程,也就是先divide再merge,用recursion的方式完成。重點在Merge這個副function中,會將目前array左右兩半,做sorting並合併的動作。作法為宣告一個與input array一樣大的array tmp,然後由左至右一個一個比較left part and right part的每一個元素,較小的就往tmp上放。完成後,再將tmp的資料放進input array中。

Reference:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php
http://alrightchiu.github.io/SecondRound/pages/about.html

Hi I am Samuel