排序(Sort)(一)

Da-Wei Chiang

大綱

• 雞尾酒排序(Cocktail Sort)
• 插入排序法(Insertion Sort)

雞尾酒排序(Cocktail Sort)

• 第一輪由左至右逐一比較, 將最大的值往右邊移
• 第二輪去除第一輪的最大值, 由右至左逐一比較, 將最小的值往左邊移
• 第三輪去除第一輪的最大值與第二輪最小值, 由左至右逐一比較, 將最大的值往右邊移
• 第四輪去除第一輪的最大值與第二輪最小值與第三輪最大值, 由右至左逐一比較, 將最小的值往右邊移
• ...等等

圖例 - 雞尾酒排序(Cocktail Sort)

圖例 - 雞尾酒排序(Cocktail Sort)

圖例 - 雞尾酒排序(Cocktail Sort)

圖例 - 雞尾酒排序(Cocktail Sort)

圖例 - 雞尾酒排序(Cocktail Sort)

練習

• 使用雞尾酒排序法將數組15, 8, 20, 18, 17, 25, 19, 5由小而大排列

插入排序法(Insertion Sort)

• 由左而右,將數組拆為左邊與右邊.左邊為已排序好的數組, 右邊是待排序的數組.
• 首先取第一個數字作為已排序的數組, 再逐一取右邊待排序數組中的一個數從左方數組後方一個一個判斷插入左邊數組中

圖例 - 插入排序法(Insertion Sort)

圖例 - 插入排序法(Insertion Sort)

圖例 - 插入排序法(Insertion Sort)

圖例 - 插入排序法(Insertion Sort)

練習

• 請使用數組[15, 8, 20, 18, 17]撰寫插入排序法, 由小到大排序