作業原理
- 首先在未排序的序列中初始化，默認最小數值為未排序的序列的起始位置，即外層回圈
- 再從除起始位置與已排序元素的剩余未排序元素中繼續尋找最小元素，然后交換起始位置的元素與最小元素，這個起始位置就成為了已排序序列的末尾元素，而且根據邏輯后面找到的第二小元素一定比最初找到的最小元素小，即內層回圈
- 然后繼續外層回圈，繼續找未排序的序列，直到所有元素排序完畢，
function selectionSort(arr){
let len=arr.length;
let minIndex,temp;
console.time('選擇排序耗時');
//外層回圈
for(let i=0;i<len-1;i++){
//每次未排序的初始位置
minIndex=i;
//剩余未排序的序列找最小值
for(let j=i+1;j<len;j++){
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
//交換起始位置與最小原始的位置
temp = arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
console.timeEnd('選擇排序耗時');
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));
-
時間復雜度:\(O(n^2)\)
-
空間復雜度:\(O(1)\)
非穩定演算法，因為同等大小的元素的相對位置發生了改變
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499522.html
標籤：其他