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

🔥@晨非辰Tong： 个人主页
👀专栏：《C语言》、《数据结构与算法入门指南》
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”

文章目录

• --引言
• 一、排序宗门：选择排序
  • 1.1 流派基本思想
• 二、 流派1：直接选择排序
  • 1.1 基本思想
    • 1.1.1 算法思路
    • 1.1.2 特性总结
  • 1.2 排序源码呈现
    • 1.2.1 残缺排序功法
    • 1.2.2 完成排序功法
  • 1.3 ==注意要点==
• 三、流派2：堆排序
  • 3.1 基本思想
    • 3.1.1 特性总结
  • 3.2 排序源码呈现
• 四、流派的决斗：直接选择 VS 堆排序
• 五、两种排序的全部源码
  • 1.直接选择排序
    • Sort.h文件
    • Sort.c文件
  • 2. 堆排序
    • Sort.h文件
    • Sort.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(N²)；
• 空间复杂度：O(1)；

1.2 排序源码呈现

1.2.1 残缺排序功法

//Sort.c文件//1）直接选择排序voidSelectSore(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);}intmain(){test01();return0;}

经过两个不同的乱序数组的直接选择排序发现，第一组成功完成排序任务，但是第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 完成排序功法

//修正voidSelectSore(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 logⁿ)；
• 空间复杂度：O(1)；

3.2 排序源码呈现

//Sort.c文件//向下调整算法voidAdjustDown(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;}}}//堆排序voidHeapSort(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);}intmain(){test01();return0;}

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

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

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

五、两种排序的全部源码

1.直接选择排序

Sort.h文件

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

Sort.c文件

//1）直接选择排序//修正voidSelectSore(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文件

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

Sort.c文件

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

结语：

选择排序一脉的"直接选择"与"堆排序"之争，揭示了算法世界的核心真理：真正的强者不仅在于思想纯粹，更在于效率卓越。

这印证了我们的编程哲学：理解每个算法的本质，才能在万千场景中做出最精准的选择。选择排序家族的这场内部较量，让我们看到了从"简单粗暴"到"精妙高效"的进化之路。

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

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

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