這章節開始我們會針對sort來詳細介紹各種不同的演算法。這章節會從最簡單的開始，也就是一般人可以想得到的方法。

Bubble Sort

從index = 0開始和下一個元素的大小，若當前元素比較大，就和下一個元素互換位置(swap)，然後index在換到下一個元素，不斷進行到最後一個元素為止，這樣是一輪，然後下一輪再從index = 0開始，只不過最後要提前一個元素結束一輪（因為最後一個位置是已經sort好的當輪最大元素）；所以每一輪都可以把較大的元素swap到最後面，並在下一輪提前一個元素結束。

Selection Sort

從當前集合中找到最小的元素，把他swap到index 0的位置，然後再從index = 1開始到最後面的集合中找出最小的元素，把他swap到index 1的位置，如此反覆直到最後。

Insertion Sort

從index = 0開始，把左半邊規劃為sorted區域，右側為un-sorted區域，所以每往前一個index時，sorted區域都會擴大，並將該元素不斷往前swap，直到它歸屬的位置。

以上三種方法其runtime應該不用多說，都會是O(log N)。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License