数据结构进阶篇之【选择排序】详细讲解（选择排序，堆排序）

在这里插入图片描述
民以食为天，我以乐为先
嘴上来的嘘寒问暖，不如直接打笔巨款

一、选择排序

1.直接选择排序 SelectSort

1.1 基本思想

1.2 实现原理

1.3 代码实现

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

2.堆排序 HeapSort

跳转链接：数据结构之堆的应用

二、完结撒❀

–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–

一、选择排序

1.直接选择排序

1.1 基本思想

original版（原始版）：

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

optimize版（优化版）：

每一次从待排序的数据元素中选出最小和最大的两个元素，分别存放在序列的起始位置和队尾位置，直到全部待排序的数据元素排完。

1.2 实现原理

这里我们讲解optimize版

在元素集合array[0]–array[n-1]中选择值最大和值小的数据元素

若最大值不是这组元素中的最后一个元素，则将它与这组元素中的最后一个元素交换，若最小值不是这组元素中的第一个元素，则将它与这组元素中的第一个元素进行交换

在剩余的array[1]–array[n-2]集合中，重复上述步骤，直到集合剩余1个元素或2个元素

因为我们完成一次循环后就可以将数组开头下标加1，结尾下标减一，所以我们需要记录下标实现交换

这里直接说明，按照上述逻辑执行到数组中剩下两个元素的时候可能会出现BUG，当剩下两个下标对应值不符合逻辑时会相互进行两次交换，但这时只进行一次交换就足够

动态图解：
在这里插入图片描述

1.3 代码实现

void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

//选择排序 同时选出最大和最小的两个数据
void SelectSort(int* a, int n)
{
		int begin = 0;
		int end = n - 1;

		while (begin<end)
		{
			int mini = begin, maxi = begin;
			//选出最大和最小值
			for (int i = begin + 1; i <= end; i++)
			{
				if (a[i] < a[mini])
				{
					mini = i;
				}

				if (a[i] > a[maxi])
				{
					maxi = i;
				}
			}

			Swap(&a[begin], &a[mini]);
			if (begin == maxi)//!!!
			{
				maxi = mini;
			}
			Swap(&a[end], &a[maxi]);
			++begin;
			--end;
		}
}