給一個數列以某排序法寫出排序過程

 有一組原始的整數序列為 56, 18, 79, 7, 42, 96, 35, 66，請分別以 Insertion sort 及Quick sort 的方法寫出將此一數列由小到大的排序過程。注意：是寫出排序的過程，不只是排序結果。

答

插入 排序過程

[56, |18, 79, 7, 42, 96, 35, 66]將未排中的18放入前面已排適當位置，18<56放在56前面。

[18,56, |79, 7, 42, 96, 35, 66]將未排中的79放入前面已排適當位置，56<79放在56後面。

[18,56,79 |7, 42, 96, 35, 66]將未排中的7放入前面已排適當位置，7<18放在18前面。

[7,18,56,79 | 42, 96, 35, 66]將未排中的42放入前面已排適當位置，42<56放在56前面。

[7,18,42,56,79 |96, 35, 66]將未排中的96放入前面已排適當位置，79<96放在79前面。

[7,18,42,56,79,96 |35, 66]將未排中的35放入前面已排適當位置，35<42放在42前面。

[7,18,35,42,56,79,96 |, 66]將未排中的66放入前面已排適當位置，66<79放在79後面。

[7,18,35,42,56,66,79,96 |]最後得已排好數列。

快速 排序過程

[56, 18, 79, 7, 42, 96, 35, 66]選42當基準值分兩區

[ 18, 7,35, |42|, 56,79,96, 66]

對數列[ 18, 7,35,]選基準值18得二分區[ 7,|18|,35,]

對於數列[56,79,96, 66]選基準值66得二分區[56,|66|,79,96]

對於數列[79,96]選基準值79得[|79|,96]

合併所有分區得[7,18,35,42,56,66,79,96]

變化題，寫出由大至小排列過程

給定數字串列，5, 3, 4, 1, 2。請利用“快速排序法”與“氣泡排序法”，將此串列由

大到小排序。

答

快

［ 5,|4|,3,1,2］

［1, |2|, 3］

合併［5,4,3,2,1］

另解：第一回合

比左邊基準值小3，右邊比基準值大沒有，所以沒比基準值大的，位置正確不用交換

|5|, 3, 4, 1, 2

第二回合

比左邊基準值小1，右邊比基準值大4，左右代理人相遇在4，與基準值交換

5,|3|, 4, 1, 2

5,|4|, 3, 1, 2

第三回合

從左邊比基準值小3，右邊比基準值大沒有，已在正確位置不用交換

5,|4|, 3, 1, 2

第四回合

從左邊比基準值小1，右邊比基準值大沒有，已在正確位置不用交換

5,4, |3|, 1, 2

第五回合

從左邊比基準值小沒有，右邊比基準值大2，相遇在2交換

5,4, 3, |1|, 2

 5, 4, 3, 2,1

氣

［5, 3, 4, 1, 2］

［5, 4,3, 2, 1］