[[427685]]

本文轉載自微信公眾號「JS每日一題」，作者灰灰。轉載本文請聯系JS每日一題公眾號。

一、是什么

選擇排序(Selection sort)是一種簡單直觀的排序算法，無論什么數據進去都是 O(n2)的時間復雜度，所以用到它的時候，數據規模越小越好

其基本思想是：首先在未排序的數列中找到最小(or最大)元素，然后將其存放到數列的起始位置

然后再從剩余未排序的元素中繼續尋找最小(or最大)元素，然后放到已排序序列的末尾

以此類推，直到所有元素均排序完畢

舉個例子，一個數組為 56、12、80、91、29，其排序過程如下：

• 第一次遍歷時，從下標為 1 的位置即 56 開始，找出關鍵字值最小的記錄 12，同下標為 0 的關鍵字 56 交換位置。此時數組為 12、56、80、91、20

• 第二次遍歷時，從下標為 2 的位置即 56 開始，找出最小值 20，同下標為 2 的關鍵字 56 互換位置，此時數組為12、20、80、91、56

• 第三次遍歷時，從下標為 3 的位置即 80 開始，找出最小值 56，同下標為 3 的關鍵字 80 互換位置，此時數組為 12、20、56、91、80

第四次遍歷時，從下標為 4 的位置即 91 開始，找出最小是 80，同下標為 4 的關鍵字 91 互換位置，此時排序完成，變成有序數組

二、如何實現

從上面可以看到，對于具有 n 個記錄的無序表遍歷 n-1 次，第i 次從無序表中第 i 個記錄開始，找出后序關鍵字中最小的記錄，然后放置在第 i 的位置上

直至到從第n個和第n-1個元素中選出最小的放在第n-1個位置

如下動畫所示：

用代碼表示則如下：

function selectionSort(arr) { 
    var len = arr.length; 
    var minIndex, temp; 
    for (var i = 0; i < len - 1; i++) { 
        minIndex = i; 
        for (var j = i + 1; j < len; j++) { 
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數 
                minIndex = j;                 // 將最小數的索引保存 
            } 
        } 
        temp = arr[i]; 
        arr[i] = arr[minIndex]; 
        arr[minIndex] = temp; 
    } 
    return arr; 
} 

第一次內循環比較N - 1次，然后是N-2次，N-3次，……，最后一次內循環比較1次 共比較的次數是 (N - 1) + (N - 2) + ... + 1，求等差數列和，得 (N - 1 + 1)* N / 2 = N^2 / 2，舍去最高項系數，其時間復雜度為 O(N^2)

從上述也可以看到，選擇排序是一種穩定的排序

三、應用場景

和冒泡排序一致，相比其它排序算法，這也是一個相對較高的時間復雜度，一般情況不推薦使用

但是我們還是要掌握冒泡排序的思想及實現，這對于我們的算法思維是有很大幫助的

參考文獻

https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/9762418

https://zhuanlan.zhihu.com/p/29889599

http://data.biancheng.net/view/72.html 

https://leetcode-cn.com/problems/sort-an-array/solution/shi-er-chong-pai-xu-suan-fa-bao-ni-man-yi-dai-gift/