选择排序

TIP

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

算法描述

• 步骤 1：将第 0 位置的元素取出，依次和后面的剩余元素比较，如果后面的元素更小就交换，以此确定第一个值就是最小值
• 步骤 2：将第 1 到 n-1 个的元素取出，按照步骤 1 依次比较调整顺序
• 步骤 3：每轮比较确定一个最小值排到前面，直到排序完成

动图演示

代码编写

// 选择排序
function selectionSort(arr) {
	// 1. 获取数组长度
	var length = arr.length

	// 2. 外层循环：从0开始获取元素，直到length-2位置
	for (var j = 0; j < length - 1; j++) {
		// 3. 内层循环：从j+1位置开始，和后面的元素进行比较
		var min = j
		for (let i = min + 1; i < length; i++) {
			// 4. 如果j位置的数据大于i位置的数据, 那么记录最小的位置
			if (arr[min] > arr[i]) {
				min = i
			}
		}

		// 5. 交换min和j位置的数据
		var tmp = arr[min]
		arr[min] = arr[j]
		arr[j] = tmp
	}

	// 6. 返回数组
	return arr
}

代码解析

文字说明

• 第一步：获取数组长度
• 第二步：使用反向遍历，编写外层循环控制冒泡趟数，为了越遍历越少：
  1. 第一次：j = 0，指定第一个元素
  2. 最后一次：j = length - 1，指定最后一个元素
• 第三步：编写内层循环负责将指定索引（i）的元素与剩下（i - 1）的元素进行比较
  1. 第一次比较： i = j + 1，依次比较到 length 为止，找到最小值，然后交换到 j 的位置

图解分析

代码测试

// 测试选择排序
var arr = [3, 6, 4, 2, 11, 10, 5]
console.log(selectionSort(arr).join("-"))
// 2-3-4-5-6-10-11

排序效率

• 比较次数：N*(N-1)/2, 也就是 O(N²)
• 交换次数：N-1, 用大 O 表示法就是 O(N)
• 选择排序通常认为在执行效率上是高于冒泡排序的