【数据结构初阶】--从“最小值筛选”到代码落地，解锁选择排序的核心思想！

晨非辰Tong

发布于 2025-12-23 15:00:08

390

文章被收录于专栏：C++C++

–引言

在算法修仙界，选择排序一脉两大功法——“直接选择”与“堆排序”，为争夺“话事人”之位已论道多年。一者大道至简，一者内蕴玄机。本期《排序算法卷二》将带您深入这场核心对决，揭晓谁能以绝对实力，执掌选择排序之牛耳。

一、排序宗门：选择排序

1.1 流派基本思想

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

二、流派1：直接选择排序

1.1 基本思想

每一趟（如第 i 趟）在后面n - i + 1个待排序的元素中选取最小（或最大)的元素，作为有序序列的第i个元素（原地操作数组），直到第n-1趟做完，待排序元素只剩下一个，就不用再选了。

1.1.1 算法思路

首先定义四个变量–> begin 指向待排序元素的首元素、end 指向待排序元素的末元素、min 指向待排序元素中的最小值（初始值想首元素）、max 指向待排序元素的最大值（初始值想首元素）。

开始进行循环遍历数组，变量begin、end 充当未排序元素的边界。每次遍历让 min 指向最小的，并且与 begin 指向的元素交换；同样，每次遍历让 max 指向最大的，并且与 end 指向的元素交换。

每交换完一次，未排序元素的边界就缩小一位：begin++、end--。

1.1.2 特性总结

直接选择排序的思考很简单，但是整体的效率有所欠缺，实际中很少用到；
时间复杂度：O(N2)；
空间复杂度：O(1)；

1.2 排序源码呈现

1.2.1 残缺排序功法

//Sort.c文件

//1）直接选择排序
void SelectSore(int* arr, int n)
{
	//定义边界变量
	int begin = 0;
	int end = n - 1;

	//总体循环：在未排序界限以内
	while (begin < end)
	{
		//定义最大值、最小值变量
		int min = begin;
		int max = begin;

		//循环寻找min、max
		//因为初始都指向begin，从begin + 1开始
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;
			}
			if (arr[i] > arr[max])
			{
				max = i;
			}
		}

		//对应交换
		Swap(&arr[begin], &arr[min]);
		Swap(&arr[end], &arr[max]);

		//遍历完一次，边界缩小
		begin++;
		end--;
	}
}

//————————————//

//test.c文件
test01()
{
	//int arr[] = {5,3,9,6,2,4};
	int arr[] = { 5,3,9,6,2,4, 7, 1, 8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("排序之前：");
	PrintArr(arr, n);
	//直接选择排序
	SelectSore(arr, n);
	printf("排序之后：");
	PrintArr(arr, n);
}
int main()
{
	test01();
	return 0;
}

经过两个不同的乱序数组的直接选择排序发现，第一组成功完成排序任务，但是第2组在中间却出现了问题，这是为什么呢？

画图看看：

当我们画完整个的循环遍历过程，就发现了问题所在：max 在 begin 的位置，Swap(arr[min], arr[begin])就覆盖了原本 max 指向的最大值。尽管已经调换了arr[min]、arr[begin] ，这个时候排序完成，但是Swap(arr[max], arr[end])又换回去了，导致排序失败。

那么就需要对 max 在 begin 进行特殊处理，加上一定的条件：当 max == begin ，提前将 max 移到 min。

1.2.2 完成排序功法

//修正
void SelectSore(int* arr, int n)
{
	//定义边界变量
	int begin = 0;
	int end = n - 1;

	//总体循环：在未排序界限以内
	while (begin < end)
	{
		//定义最大值、最小值变量
		int min = begin;
		int max = begin;

		//循环寻找min、max
		//因为初始都指向begin，从begin + 1开始
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;
			}
			if (arr[i] > arr[max])
			{
				max = i;
			}
		}

		//对应交换
		if (max == begin)
		{
			max = min;
		}

		Swap(&arr[begin], &arr[min]);
		Swap(&arr[end], &arr[max]);

		//遍历完一次，边界缩小
		begin++;
		end--;
	}
}

1.3 注意要点

数据边界的确定：begin、end；
max与begin重合，导致调换重复。

三、流派2：堆排序

对于堆排序，想必大家都不陌生，在前面对于堆的专题学习中已经进行了堆排序的实现具体操作。

3.1 基本思想

堆排序是一种高效的比较型排序算法，其核心思想是利用“堆”这种数据结构进行排序。

堆排序分为两个主要阶段：首先将待排序的序列建成大堆（升序），此时堆顶元素为最大值；然后反复的将堆顶元素与堆末尾元素交换，并将堆的大小减一，再对新的堆顶元素进行调整维持大堆的性质，直到堆中只剩一个元素。这样每次都将当前最大值放到正确位置，最终完成排序。

3.1.1 特性总结

时间复杂度：O(n logn)；
空间复杂度：O(1)；

3.2 排序源码呈现

//Sort.c文件

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)//传父节点下标、有效数据个数
{
	int child = parent * 2 + 1;

	while (child < n)//child超过n，代表没有子节点了
	{
		//大堆结构：<，小堆结构: >
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
 
		//孩子和父亲比较
		//大堆结构：>，小堆结构:<
		if (arr[child] < arr[parent])
		{
			//父子调换
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else 
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int* arr, int n)
{
 
	//向下调整算法——建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
 
	//实现排序--升序数组
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);//logn
		end--;
	}
}
 
 //——————————————//
 
//test.c文件

test01()
{
	//int arr[] = {5,3,9,6,2,4};
	int arr[] = { 5,3,9,6,2,4, 7, 1, 8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("排序之前：");
	PrintArr(arr, n);
	//堆排序
	HeapSort(arr, n);
	printf("排序之后：");
	PrintArr(arr, n);
}
int main()
{
	test01();
	return 0;
}

四、流派的决斗：直接选择 VS 堆排序

综合评判：谁才是选择排序的「话事人」？

特性维度	直接选择排序	堆排序	胜出方
时间复杂度	O(n²)	O(n log n)	堆排序
空间复杂度	O(1)	O(1)	势均力敌
实现复杂度	简单直观	相对复杂	直接选择排序
实际应用	应用极少，主教学	应用广泛	堆排序

综合对比后：堆排序胜出！ 在算法修仙界中，堆排序凭借其稳定的高性能，当之无愧成为选择排序家族的「话事人」！

五、两种排序的全部源码

1.直接选择排序

Sort.h文件

//打印
void PrintArr(int* arr, int n);
//调换
Swap(int* x, int* y);
//1）直接选择排序
void SelectSore(int* arr, int n);

Sort.c文件

//1）直接选择排序
//修正
void SelectSore(int* arr, int n)
{
	//定义边界变量
	int begin = 0;
	int end = n - 1;

	//总体循环：在未排序界限以内
	while (begin < end)
	{
		//定义最大值、最小值变量
		int min = begin;
		int max = begin;

		//循环寻找min、max
		//因为初始都指向begin，从begin + 1开始
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;
			}
			if (arr[i] > arr[max])
			{
				max = i;
			}
		}

		//对应交换
		if (max == begin)
		{
			max = min;
		}

		Swap(&arr[begin], &arr[min]);
		Swap(&arr[end], &arr[max]);

		//遍历完一次，边界缩小
		begin++;
		end--;
	}
}

2. 堆排序

Sort.h文件

//打印
void PrintArr(int* arr, int n);
//向下调整算法
void AdjustDown(int* arr, int parent, int n);//传父节点下标、有效数据个数
//堆排序
void HeapSort(int* arr, int n);

Sort.c文件

//向下调整算法
void AdjustDown(int* arr, int parent, int n)//传父节点下标、有效数据个数
{
	int child = parent * 2 + 1;

	while (child < n)//child超过n，代表没有子节点了
	{
		//大堆结构：<，小堆结构: >
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}

		//孩子和父亲比较
		//大堆结构：>，小堆结构:<
		if (arr[child] < arr[parent])
		{
			//父子调换
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int* arr, int n)
{

	//向下调整算法——建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	//实现排序--升序数组
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);//logn
		end--;
	}
}

–总结

🍓 我是晨非辰Tong！若这篇技术干货帮你打通了学习中的卡点：
👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长
❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量
⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用
💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑
🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解
技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！

结语：

选择排序一脉的"直接选择"与"堆排序"之争，揭示了算法世界的核心真理：真正的强者不仅在于思想纯粹，更在于效率卓越。这印证了我们的编程哲学：理解每个算法的本质，才能在万千场景中做出最精准的选择。选择排序家族的这场内部较量，让我们看到了从"简单粗暴"到"精妙高效"的进化之路。

希望这篇分析能让你对选择排序流派有了更立体的认识。别忘了在评论区留下你的看法： ➤ 实战中，你会更倾向于使用哪种算法？为什么？ ➤ 你还想了解哪些排序算法的对比分析？

【往期回顾】：【数据结构】我在修仙界学排序算法之“直接宗与“希尔宗”，谁才是效率王者？

【下期预告】：交换排序家族风云再起——"冒泡排序"能否抵挡"快速排序"的强势挑战？敬请期待《卷三：交换排序论剑》！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度