【C语言/数据结构】排序（选择排序，推排序，冒泡排序）

秦jh

发布于 2024-01-29 08:58:39

690

发布于 2024-01-29 08:58:39

文章被收录于专栏：c语言，c++c语言，c++

前言

💬 hello! 各位铁子们大家好哇。 今日更新了选择，堆，冒泡排序的内容 🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

选择排序

过程图如下：

代码呈现

//时间复杂度：O(N^2)
//最好情况下：O(N^2)
void SelectSort(int* a, int n)
{
	int begin = 0, 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]);
		//当max在begin的位置时
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

分析：开始时，begin指向首元素，end是末尾元素下标。这里的选择排序与上图过程略有差异，这里的选择排序每次选出最大和最小值，分别与头和尾交换。然后begin++和end--来缩小选择的范围。需注意，在同时选最大和最小时，要判断max是否在begin的位置上，如果是，就要把maxi改为mini的值。

堆排序

代码呈现

void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		//假设左孩子小，如果假设错了，就更新一下
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//升序
void HeapSort(int* a, int n)
{
	//建大堆
	//O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

堆排序在前面的文章中已经讲解，这里不再介绍。

交换排序

冒泡排序

//时间复杂度：O(N^2)
//最好情况：O(N);
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = true;
			}
		}
		if (exchange == false)
			break;
	}
}