[Algorithm] Selection Sort (選擇排序法)
前言
因公司業務受疫情影響, 在 7 月中解散工程團隊
至今也休息了一個多月
最近開始複習一些經典演算法, 順便做個筆記
Selection Sort 說明
以下轉自維基 選擇排序
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
簡單說就是，將資料分成已排序、未排序
由未排序中找最小值(or 最大值)，加入到已排序部份的末端
最後已排序結果會是由小到大(or 由大到小)的順序排序
範例程式碼
Ruby 範例
附上 Ruby 的 online sandbox，有興趣可以把 code 貼進去玩玩看
a = [9, 8, 6, 1, 2, 10, 5, 4, 3, 7]
def selection_sort(array)
n = array.size - 1
n.times do |index|
temp_item, temp_index = array[index], index
for i in index...array.size
temp_item, temp_index = array[i], i if array[i] < temp_item
end
array[index], array[temp_index] = array[temp_index], array[index]
end
array
end
selection_sort(a)
結果如下
JavaScript 範例
JavaScript 的 online sandbox，有興趣可以把 code 貼進去玩玩看
const a = [9, 8, 6, 1, 2, 10, 5, 4, 3, 7]
const selectionSort = (array) => {
const count = array.length;
for (let i = 0; i < count; i++) {
let min = i;
for (let j = i + 1; j < count; j++) {
if (array[j] < array[min]) {
min = j;
}
}
if (min !== i) {
let temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
return array;
}
console.log(selectionSort(a))
結果如下
