排序算法之直接选择排序【图文详解】

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

在这里插入图片描述

                        博主主页：LiUEEEEE
                        C语言专栏
                       数据结构专栏
                      力扣牛客经典题目专栏

1、直接选择排序的基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2、直接选择排序的排序方法

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素。
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

其过程示意图如下所示，例如示例数组，15，36，26，27，19，10：

在这里插入图片描述
如上图所示。经过第一次筛选后，将数组中最大的一项与最后一项进行了交换，而后的筛选只需在前n - 1项中选择，并将选择出来的最大数放在第n - 1个位置（位置代号是指逻辑上的位置，并非数组下标）。

在进行依次筛选演示，将第一次筛选完毕的数组进行第二次筛选，示意图及结果如下所示：
在这里插入图片描述
以此类推，直到筛选数组仅剩一个元素时，直接选择排序就完成了。

其代码示意图如下所示

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	
	for (int i = 0; i < n; i++)
	{
		int max = 0;
		for (int j = 0; j < n - i; j++)
		{
			if (a[max] < a[j])
			{
				max = j;
			}
		}
		Swap(&a[max], &a[n - i - 1]);
	}
}

直接选择排序的特性总结：

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

3、直接选择排序的优化

上文中通俗易懂的展示了直接选择排序的方法，但其方法效率在不够高，每一次只筛选出了最大或最小的数来进行交换，对此可以进行优化：

将原本筛选最大或最小的数改为一次筛选就可以筛选出最大和最小的数，并根据数组升序或降序的要求对其进行数组交换，其具体代码如下所示：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* arr, int size)
{
	int begin = 0, end = size - 1;

	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		int flg = 0;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[maxi] < arr[i])
			{
				maxi = i;
				flg = 1;
			}
			if (arr[mini] > arr[i])
				mini = i;
		}
		Swap(&arr[begin], &arr[mini]);
		if(flg)
			Swap(&arr[end], &arr[maxi]);
		++begin;
		--end;
	}
}