作為一個程序員，一些基本的排序算法是必須要掌握的。以前人們總覺得算法是后端程序員去學(xué)的，前端只需要專注于網(wǎng)頁的美觀以及 JS 的基本邏輯交互就行，然而，近幾年隨著前端行業(yè)的發(fā)展，前端越來越注重邏輯交互，如果你還像很久之前那樣只知道用 HTML + CSS 去構(gòu)建網(wǎng)頁，那就落伍了。如今，前端程序員也需要對算法有一定的了解，不說別的，多掌握點東西總是好的。今天的文章介紹的是排序算法中的選擇排序。
什么是排序
維基百科中這樣說明：一種能將一串?dāng)?shù)據(jù)依照特定排序方式進行排列的一種算法。生活中也有很多排序的例子：超市購物排隊，學(xué)生成績排序，班級座位排序等。排序可以分為內(nèi)部排序還有外部排序。內(nèi)部排序是指待排序列完全存放在內(nèi)存中所進行的排序過程，適合不太大的元素序列；外部排序能夠處理極大量數(shù)據(jù)的排序算法，通常需要結(jié)合外存儲器（硬盤）使用。
什么是選擇排序
我的理解是選擇排序在于 “選擇” ，即先找到待排序數(shù)組中最?。ㄒ部梢允亲畲螅┑臄?shù)，然后把它排到數(shù)組的最前面，接著繼續(xù)找最?。ㄗ畲螅┑臄?shù)，然后依次排在前面排好的數(shù)后面。舉個例子可能方便理解一點，在讀小學(xué)的時候，剛開學(xué)老師要排座位，老師的考慮是讓高個子的同學(xué)坐后面，矮個子的坐前一點，這樣看黑板就不會被擋了，于是老師把同學(xué)們排成一排，一眼望去，找到最矮的小明，叫他站到前面去，接著又在剩下的人中找到最矮的小方，讓他排在小明后邊，重復(fù)這樣找下去，直到所有的同學(xué)都按照從矮到高的順序排列好，就可以分配座位了。選擇排序的過程大致如此。
實現(xiàn)代碼
以下是選擇排序的代碼：
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
console.time('選擇排序耗時');
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //尋找最小的數(shù)
minIndex = j; //將最小數(shù)的索引保存
}
}
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));
// 選擇排序耗時: 0.327880859375ms
// 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50
代碼中使用了一個臨時變量 temp 來交換兩個數(shù)，用 minIndex 來表示找到的最小的數(shù)的索引，當(dāng)后面一個數(shù)比這個最小的數(shù)還要小時，那么將這個數(shù)的小標(biāo)賦給 minIndex ，然后將它跟前面的數(shù)交換位置，這樣的話，每次循環(huán)，我們就會找到最小的一個數(shù)，然后將它與當(dāng)前遍歷到的數(shù)互換，等遍歷完的時候，基本上就排好啦。
時間和空間復(fù)雜度
最好的情況：T(n) = O(n2)
最壞的情況：T(n) = O(n2)
平均時間復(fù)雜度是：T(n) = O(n2)
空間復(fù)雜度為：O(1)
引用
維基百科： https://zh.wikipedia.org/wiki/
代碼出處： https://blog.csdn.net/jizhen_tan/article/details/52555639
