面試官：說說你對(duì)選擇排序的理解？如何實(shí)現(xiàn)？應(yīng)用場(chǎng)景？
本文轉(zhuǎn)載自微信公眾號(hào)「JS每日一題」，作者灰灰。轉(zhuǎn)載本文請(qǐng)聯(lián)系JS每日一題公眾號(hào)。
一、是什么
選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法，無論什么數(shù)據(jù)進(jìn)去都是 O(n2)的時(shí)間復(fù)雜度，所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好
其基本思想是：首先在未排序的數(shù)列中找到最小(or最大)元素，然后將其存放到數(shù)列的起始位置
然后再從剩余未排序的元素中繼續(xù)尋找最小(or最大)元素，然后放到已排序序列的末尾
以此類推，直到所有元素均排序完畢
舉個(gè)例子，一個(gè)數(shù)組為 56、12、80、91、29，其排序過程如下：
- 第一次遍歷時(shí)，從下標(biāo)為 1 的位置即 56 開始，找出關(guān)鍵字值最小的記錄 12，同下標(biāo)為 0 的關(guān)鍵字 56 交換位置。此時(shí)數(shù)組為 12、56、80、91、20
- 第二次遍歷時(shí)，從下標(biāo)為 2 的位置即 56 開始，找出最小值 20，同下標(biāo)為 2 的關(guān)鍵字 56 互換位置，此時(shí)數(shù)組為12、20、80、91、56
- 第三次遍歷時(shí)，從下標(biāo)為 3 的位置即 80 開始，找出最小值 56，同下標(biāo)為 3 的關(guān)鍵字 80 互換位置，此時(shí)數(shù)組為 12、20、56、91、80
第四次遍歷時(shí)，從下標(biāo)為 4 的位置即 91 開始，找出最小是 80，同下標(biāo)為 4 的關(guān)鍵字 91 互換位置，此時(shí)排序完成，變成有序數(shù)組
二、如何實(shí)現(xiàn)
從上面可以看到，對(duì)于具有 n 個(gè)記錄的無序表遍歷 n-1 次，第i 次從無序表中第 i 個(gè)記錄開始，找出后序關(guān)鍵字中最小的記錄，然后放置在第 i 的位置上
直至到從第n個(gè)和第n-1個(gè)元素中選出最小的放在第n-1個(gè)位置
如下動(dòng)畫所示：
用代碼表示則如下：
- 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]) { // 尋找最小的數(shù)
- minIndex = j; // 將最小數(shù)的索引保存
- }
- }
- temp = arr[i];
- arr[i] = arr[minIndex];
- arr[minIndex] = temp;
- }
- return arr;
- }
第一次內(nèi)循環(huán)比較N - 1次，然后是N-2次，N-3次，……，最后一次內(nèi)循環(huán)比較1次 共比較的次數(shù)是 (N - 1) + (N - 2) + ... + 1，求等差數(shù)列和，得 (N - 1 + 1)* N / 2 = N^2 / 2，舍去最高項(xiàng)系數(shù)，其時(shí)間復(fù)雜度為 O(N^2)
從上述也可以看到，選擇排序是一種穩(wěn)定的排序
三、應(yīng)用場(chǎng)景
和冒泡排序一致，相比其它排序算法，這也是一個(gè)相對(duì)較高的時(shí)間復(fù)雜度，一般情況不推薦使用
但是我們還是要掌握冒泡排序的思想及實(shí)現(xiàn)，這對(duì)于我們的算法思維是有很大幫助的
參考文獻(xiàn)
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/
