前端工程師演算法系列(2)-選擇排序
來自專欄前端學習指南
22 人贊了文章
選擇排序
一、原理解析
第一輪：從數組中找到最小的數字，和第一個數字交換位置
第二輪：從第二個數字開始，找到最小的數字，和第二個數字交換位置
...
就像排隊一樣，每次從未排好的隊伍中「選擇」一個最矮的，依次放到隊伍的第一位、第二位...
二、範例演示
以下表格里，紅色表示選中的待排序的數字，藍色表示最終排好的數字。
第一輪：
- 數組中找到最小值 3， 和數組第一個數10交換位置
第二輪：
- 從第二個數開始，數組中找到最小值 10， 和數組第二個數34交換位置
第三輪：
- 從第三個數開始，數組中找到最小值 21， 和數組第三個數21交換位置(自己不用交換)
...
三、實現方式
function sectionSort(arr) { for(let min = i = 0; i < arr.length /*i代表輪數*/; i++) { min = i for(let j = i + 1; j < arr.length; j++) { if(arr[min] > arr[j]) { min = j } } [ arr[i], arr[min] ] = [ arr[min], arr[i] ] //把每輪的第一個和當前輪的最小值交換位置 }}var arr = [10, 34, 21, 47, 3, 28]sectionSort(arr)console.log(arr)
四、效率測試
下面我們測試排序性能。以下的代碼中，randomArr 函數會生成一個隨機數組， 數組長度默認是100， 最大值默認值是1000。 console.time 和 console.end 用來記錄排序時間。
let arr = randomArr(10000, 100)console.time(sectionSort)sectionSort(arr)console.timeEnd(sectionSort)function randomArr( arrLen = 100, maxValue = 1000 ) { let arr = [] for(let i = 0; i < arrLen; i++) { arr[i] = Math.floor((maxValue+1)*Math.random()) } return arr}function sectionSort(arr) { for(let min = i = 0; i < arr.length /*i代表輪數*/; i++) { min = i for(let j = i + 1; j < arr.length; j++) { if(arr[min] > arr[j]) { min = j } } [ arr[i], arr[min] ] = [ arr[min], arr[i] ] //把每輪的第一個和當前輪的最小值交換位置 }}
經1000次測試，可以得出結論，數組長度增加10倍，排序時間約增加100倍
五、複雜度分析
時間複雜度為 O(n^2) ，和上面的測試基本一致。
本文作者若愚，如果覺得不錯，高抬貴指點個贊。或者發現文章中的錯誤，或者有更好的建議，歡迎演算法交流群交流，點此掃碼進群。
推薦閱讀：