数据结构与算法-排序(二)选择排序(Selection Sort)

摘要

选择排序的逻辑是先遍历比较出序列中最大的,然后把最大的放在最后位置。

遵循这个逻辑,用代码实现时,做到1.减少比较次数之外,这里引入一个新的指标 - 稳定性,2.保证排序过程中的稳定性也是一个优化处理

代码逻辑

  1. 从头遍历序列,分别和尾部元素比较,记录最大的元素坐标
  2. 遍历完成后,和尾部位置交换位置
  3. 忽略尾部已经交换的元素,执行 1 和 2 步骤

实现

依据逻辑来看,最大值是放在尾部,并放置后,下次循环排除这个放置最大值的位置,for 循环从尾部开始最合适。

小循环开始前,需要先创建变量记录最大值坐标,这里使用的是 0 位置坐标,那么小循环开始时,就可以直接从 1 位置遍历,这就减少比较次数

	for (int end = array.length-1; end > 0; end--) {
		int maxIndex = 0;
		for (int begin = 1; begin <= end; begin++) {
			if (cmp(maxIndex, begin) < 0) {
				maxIndex = begin;
			}
		}
		swap(maxIndex, end);
	}

进阶

开始前,先解释一下稳定性,稳定性是尽量保持序列中两个元素在排序前和排序后的相对位置。比如下面伪代码:


// a1 与 a2 的值相等
a1 = a2 = 3

// 序列中 a1 值的位置在 a2 前面
array = [5, a1, 4, a2, 2]

// 排序之后, a1 值位置在 a2 前面,保持了稳定性
array = [2, a1, a2, 4, 5]

为什么稳定性重要?

序列中需要保证多次排序后数据位置的相对稳定。比如信息表中,以 age 从小到大排序,不希望 age 相等的一组数据中,它的名称在每一次排序之后都会有不同的顺序。

稳定性的优化

这里为了保证排序之后的稳定性,就当出现最大值时,也更新最大值的坐标。

为什么这样就可以保证稳定性?

首先最大值被交换到尾部之后,下次遍历比较的时候,就不再比较这个位置,小循环的比较是从头开始的,如果出现等于最大值时,不更新最大值的位置,排序之后,相等的值,最靠前的值就被放在了最后面,改变了之前序列中相等值的相对位置。

	for (int end = array.length-1; end > 0; end--) {
		int maxIndex = 0;
		for (int begin = 1; begin <= end; begin++) {
			if (cmp(maxIndex, begin) <= 0) { // 保证稳定性
				maxIndex = begin;
			}
		}
		swap(maxIndex, end);
	}

时间和空间复杂度

  • 最好、平均、最坏时间复杂度:O(n^2),n 的 2 次方
  • 空间复杂度:O(1)
  • 属于稳定排序
上一篇:element ui table 二次封装


下一篇:Machine-Learning–Based Column Selection for Column Generation