玖叶教程网

一、 选择排序概述

选择排序(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)