C语言选择排序详解：直接选择与堆排序实现

直接选择排序的原理与优化

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

第1步：理解算法执行逻辑

在数组集合 a[i]...a[n-1] 中，首先找出关键码最大或最小的数据元素。若该元素不是当前区间的第一个（或最后一个）元素，则将其与区间端点元素交换。随后在剩余的子集中重复此过程，直至集合剩余元素不足两个。

通过实例观察其运算过程有助于建立直观认知：

第2步：掌握优化版代码实现

传统的直接选择排序每趟只确定一个极值，优化版本在一次遍历中同时选出最大数和最小数，并将它们分别交换到序列的两端，从而减少遍历次数，提升效率。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
//交换函数
void Swap(int* mini, int* maxi)
{
	int tmp = *mini;
	*mini = *maxi;
	*maxi = tmp;
}
 
//打印函数
void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
 
//直接选择排序（优化版）
void SelectSort(int *a,int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = end;
		//在一次遍历中选出最大和最小的下标
		for (int i=begin;i<=end;++i)
		{
			if (a[i]>a[mini])//记录最小值的下标（注意此处逻辑应为找小，原代码注释可能有误，通常升序找小）
			{
				mini = i;   
			}
			if (a[i] <a[maxi])//记录最大值的下标
			{
				maxi = i;
			}
		}
		//交换最小值到 begin 位置
		Swap(&a[begin],&a[mini]);
        //特殊情况处理：如果 begin 本身就是最大值的位置
        //第一次交换后，min位置的值变成了原来的最大值，所以maxi需要更新为mini
        if (begin == maxi)
		{
			maxi = mini;
		}
		//交换最大值到 end 位置
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}
 
int main()
{
	int a[10] = { 3,5,9,7,4,2,1,6,0,8 };
	SelectSort(a, sizeof(a) / sizeof(a[0]));
	Print(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

第3步：分析直接选择排序特征

• 适用场景：算法逻辑简单易懂，但因效率不高，实际工程中较少作为首选排序方案。
• 时间复杂度：O(N^2)。无论数据初始顺序如何，都需要遍历至结束进行比较。
• 空间复杂度：O(1)。仅需常数级额外空间。
• 稳定性：不稳定。交换操作可能打乱相等元素的相对顺序。

堆排序的实现与优势

堆排序（Heapsort）是利用堆积树（堆）这种数据结构设计的排序算法，属于选择排序的进阶形态。它通过维护堆的性质来高效地选出极值元素。

第1步：理解堆的结构与判定

堆通常是一棵完全二叉树。满足所有父亲节点值大于等于孩子节点的称为大根堆（用于升序排列），反之则为小根堆（用于降序排列）。

判断一个数组是否构成堆，需验证是否满足父与孩子的大小关系：

当输入数组无序时，直接使用堆排序需要先进行“建堆”操作。遵循原则：“建小堆排降序，建大堆排升序”。通常为了方便理解，我们常以建小堆为例，或根据需求调整比较符号。

第2步：掌握向下调整算法

向下调整算法（AdjustDwon）是建堆的核心。前提是左右子树已经满足堆性质。从根节点开始，比较左右孩子，选出较小（或小堆情况下的极值）的那个与父亲比较。若孩子更优则交换，并继续向下调整，直至到达叶子节点或不再需要交换。

第3步：执行自底向上建堆

建堆并非从根节点开始调整，而是从最后一个非叶子节点（即倒数第二层最右侧节点）开始，自左向右、自下而上地对每个节点执行向下调整算法，最终使整棵树成为堆。

第4步：完整代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

//打印数据
void Printf(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
}
 
//交换
void Swap(int* child, int* parent)
{
	int tmp = *child;
	*child = *parent;
	*parent = tmp;
}

//向下调整算法：建立小堆（用于排降序示例，若排升序需改为大堆逻辑）
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1; // 默认取左孩子
	while (child < n)
	{
		// 选出左右孩子中较小的那个
		if (child+1 < n && a[child + 1] < a[child])
		{
			child += 1;
		}
		// 如果孩子小于父亲，则交换并继续向下
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break; // 满足堆性质，停止调整
		}
	}
}

//堆排序主逻辑
void HeapSort(int *a,int n)
{
	// 1. 建堆：从最后一个非叶子节点开始向前调整
	// 最后一个非叶子节点索引为 (n-1-1)/2
	for (int i=(n-1-1)/2;i>=0;--i)
	{
		AdjustDwon(a,n,i);
	}
    
    // 2. 排序：将堆顶元素（极值）与末尾元素交换，并重新调整堆
	int end = n - 1;
	while (end>0)
	{
		Swap(&a[0],&a[end]); // 交换堆顶和末尾
		AdjustDwon(a,end,0);   // 对剩余的 n-1 个元素重新建堆（范围缩小）
		--end;
	}
}

int main()
{
	int a[10] = {9,2,5,4,3,1,6,7,8,0};
	HeapSort(a,sizeof(a) / sizeof(a[0]));
	Printf(a,sizeof(a) / sizeof(a[0]));
	return 0;
}

排序过程的可视化演示如下：

第5步：分析堆排序特性

• 性能优势：相比直接选择排序，堆排序利用堆结构选数，效率大幅提升，适合大数据量排序。
• 时间复杂度：O(N log N)。建堆耗时 O(N)，每次调整耗时 O(log N)，共进行 N-1 次调整。
• 空间复杂度：O(1)。原地排序，无需额外内存。
• 稳定性：不稳定。堆的调整和交换过程会破坏相等元素的原始相对顺序。

以上就是C语言选择排序（直接选择排序与堆排序）的详细内容，更多关于C语言数据结构与算法的资料请关注本站其它相关文章！