# 选择排序

TIP

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

# 算法描述

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

# 动图演示

sort

# 代码编写

// 选择排序
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 的位置

图解分析

sort

# 代码测试

// 测试选择排序
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)
  • 选择排序通常认为在执行效率上是高于冒泡排序的