一、 选择排序概述

选择排序(Selection Sort)是从待排序数列中取出最小(或最大)的1位，与第一个位置交换，再从待排序数列中找出最小的跟整个数列的第二个交换。以此类推遍历完待排序数列。平均算法复杂度：O(n^2)

步骤是：

1、 先建立两个循环，外循环用于逐个交换数据，内循环用来遍历找到最小(或最大)值。

2、 设第1项为最小值，在内循环中将其逐个与后项进行比较，如果遇到更小的值，则更新最小值，并记录下最小值的下标。

3、 在外循环中将第1项与最小值进行交换，然后以第2项作为最小值，再重复执行步骤2，直到遍历完全部待排序区间。

二、 选择排序执行过程分析

三、 选择排序实现

1. 标准实现

function selectionSort(arr) { console.time('time') var min, minIdx, tmp var l = arr.length for (var i = 0; i < l - 1; i++) { min = arr[i] minIdx = i for (var j = i + 1; j < l; j++) { // 找到并记录下最小值和位置 if (arr[j] < min) { min = arr[j] minIdx = j } } console.log(min, minIdx, arr) // 将待排序里最小值交换到已排序最后面 if (minIdx !== i) { tmp = arr[i] arr[i] = min arr[minIdx] = tmp } } console.timeEnd('time') return arr}var arr = [4, 6, 2, 1, 8, 9, 7, 3, 5, 9, 4]selectionSort(arr)

标准实现

function selectionSort(arr) { console.time('time') var min, minIdx, tmp, newArr = [] var l = arr.length for (var i = 0; i < l; i++) { min = arr[i] minIdx = i for (var j = 0; j < l; j++) { // 找到并记录下最小值和位置 if (arr[j] < min) { min = arr[j] minIdx = j } } console.log(min, minIdx, arr) // 将待排序里最小值添加到新数组中去 newArr.push(min) arr.splice(minIdx, 1) l-- i-- } console.timeEnd('time') return newArr}var arr = [4, 6, 2, 1, 8, 9, 7, 3, 5, 9, 4]selectionSort(arr)