【数据结构初阶】--排序（二）：直接选择排序，堆排序

用户11915063

发布于 2025-11-19 19:09:00

100

前言：上篇博客我们学习了直接插入排序和希尔排序，对排序有了一定的理解，之前树与二叉树的博客我们还学习了堆排序，那么今天我们就进入直接选择排序和堆排序的学习中

一、直接选择排序

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

在实现选择排序之前，我们还需要先实现一下交换的函数

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

我们如果只选最小或最大值的话那时间复杂度肯定就是O(n)，我们可以优化一下，让它们同时选择最大值和最小值

代码展现：

//直接选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//交换
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);

		begin++;
		end--;
	}
}

图解：

test.c:

#include"Sort.h"
 
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
void test1()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int size = sizeof(a) / sizeof(a[0]);
	printf("排序前:");
	PrintArr(a, size);
 
	//直接选择排序
	SelectSort(a, size);
 
	printf("排序后:");
	PrintArr(a, size);
}
 
int main()
{
	test1();
	return 0;
}

测试结果：

测试完成，打印没有问题，升序排列正确，退出码为0

复杂度分析：

时间复杂度：O(n^2) 直接选择排序在实际运用中比较少 ,因为它的性能很小

二、堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的一种，它通过堆来进行选择数据，需要注意的是排升序要建大堆，排降序建小堆。

堆排序在之前二叉树(三)的博客中讲的很详细，给大家看一下它的代码和时间复杂度吧，在实现之前我们需要用到向下调整算法和交换函数，交换在上面实现过了，这里先把向下调整算法的代码展示给大家

向下调整算法（建大堆版）:

//向下调整
void AdjustDown(int* arr, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{ 
		//找大的孩子
		//建大堆 <
		//建小堆 >
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		//孩子和父亲比较
		//建大堆 <
		//建小堆 >
		if (arr[parent] < arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

代码实现：

void HeapSort(int* arr, int n)
{
	//向下调整算法--建堆 时间复杂度O(n）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);//因为这里建的是小堆，所以向下调整，就成了降序
	}

	//向上调整算法--建堆  时间复杂度O(n*logn)
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/
	//n* logn
	int end = n - 1;

	while (end > 0)//循环取最后一个元素与顶交换，再向下调整
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

test.c:

#include"Sort.h"
 
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
void test1()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int size = sizeof(a) / sizeof(a[0]);
	printf("排序前:");
	PrintArr(a, size);
 
	//直接插入排序
	//InsertSort(a, size);
	//希尔排序
	//ShellSort(a, size);
	//直接选择排序
	//SelectSort(a, size);
	//堆排序
	HeapSort(a, size);
 
	printf("排序后:");
	PrintArr(a, size);
}
 
 
int main()
{
	test1();
	return 0;
}

测试结果：

测试完成，打印没有问题，升序排序正确，退出码为0

复杂度分析：

时间复杂度:O(n*logN)

三.直接选择排序和堆排序的性能对比

我们还是通过测试来对比一下这两种排序的性能，大家也可以看看和之前实现过的排序的对比

代码展示：

#include"Sort.h"
 
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
void test1()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int size = sizeof(a) / sizeof(a[0]);
	printf("排序前:");
	PrintArr(a, size);
 
	//直接插入排序
	//InsertSort(a, size);
	//希尔排序
	//ShellSort(a, size);
	//直接选择排序
	//SelectSort(a, size);
	//堆排序
	HeapSort(a, size);
 
	printf("排序后:");
	PrintArr(a, size);
}
 
// 测试排序的性能对⽐
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
 
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
	}
 
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
 
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
 
	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
 
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
 
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
 
	free(a1);
	free(a2);
	free(a3);
	free(a4);
}
 
int main()
{
	TestOP();
	//test1();
	return 0;
}