【排序算法】③直接选择排序

前言

直接选择排序比较简单，实现起来较容易，但是直接选择排序与直接插入排序的区别难以理清，笔者下方整理一个表格供参考。

一、直接选择排序是什么？

算法思想

直接选择排序的思想是： 每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。 通过不断选择剩余元素中的最小者来实现排序。

直接选择排序为什么能实现排序？ 很好理解，假设i=0是数组下标，n是数据个数。直接选择排序就是简单粗暴的从未排序的数据集中挑出最小/最大，放在第i个位置处，i++，未排序的数据个数就变成n-i个，重复直到i==n-1（数组下标）。

二、实现直接选择排序

博主这里以升序为例：

void SelectionSort(int* a, int n)
{
	if (!a)return;

	for (int i = 0; i < n; ++i)
	{
		int _min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[_min])_min = j;
		}
		swap(&a[i], &a[_min]);
	}
}

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

依据算法，从数据集中，挑选处特征码最小/最大的数据放在已排序的末尾。

①_min变量用于存储合适数据的下标。从第i号，到之后的未排数据中选择最小或最大的数据，_min保存其下标，等内循环结束交换数据值；

②外循环，每一次循环的目的是在未排数据中寻找最小/最大的值；内循环，作用是依次拿未排数据与a[i]比较大小。

三、分析直接选择排序

直接选择排序的特征

1. 直接选择排序非常好理解，但是效率不是很好，故实际中很少使用； 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：不稳定。

与直接插入排序的区别

直接选择排序与直接插入排序的区别是什么？

直接选择排序： 每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。 通过不断选择剩余元素中的最小者来实现排序。

直接插入排序： 将未排序部分的元素逐个插入到已排序部分的适当位置。 即，将元素插入到已排序序列中的正确位置，从而逐步构建有序序列。

总结

本文是【排序算法】系类第三篇，直接选择排序较为简单故篇幅较短。

来不及怀念直接选择排序了，接下来登场的是常用且效率高、结构较复杂的另一种选择排序算法：堆排序！