当前位置：首页 > article >正文

算法 -选择排序

article 2024/11/13 9:35:53

博客主页：【夜泉_ly】
本文专栏：【算法】
欢迎点赞👍收藏⭐关注❤️

在这里插入图片描述

文章目录

💡选择排序
- 1. 🔄 选择排序
- - 🖼️示意图
  - 📖简介
  - 💡实现思路1
  - 💻代码实现1
  - 💡实现思路2
  - 💻代码实现2
- 2. 🏰 堆排序
- - 🖼️示意图
  - 📖简介
  - 💡实现思路
  - 💻代码实现

💡选择排序

选择排序分为选择排序和堆排序。

1. 🔄 选择排序

🖼️示意图

$选择排序 - 示意图$
在这里插入图片描述

📖简介

选择排序是一种比较简单直观的排序，其思想就是不断从待排序的数组中选出符合要求的数据。

由于每次选数要遍历一遍数组，而重复次数为数组长度，因此时间复杂度为 $O(N^2)$ 。实际用处不大，因为它不会管数据长什么样，都会从头遍历到尾，不如直接插入排序。这也给了我们一个启示：斗地主发牌时，要边拿牌边排序(插入排序)，不能拿到一把牌后再排序(选择排序)。

💡实现思路1

定义一个指针 end ，初始为-1，表示已排序数组的结束位置。(最开始还没有选出最小值，所以是 -1)
选择，用一个指针 cur 从end + 1遍历到尾，用另一个指针 min 记录最小值的位置。
交换，将 end + 1 处的值与 min 处的值交换。
end++，继续下一轮。
结束条件为 end >= size - 1 ，即所有元素都已排序。

💻代码实现1

void SelectSort(int* arr, int size)
{
	int end = -1;
	while (end < size - 1)
	{
		int cur = end + 1;
		int min = cur;
		while (cur < size)
		{
			if (arr[cur] < arr[min])min = cur;
			cur++;
		}
		swap(arr[end + 1], arr[min]);
		end++;
	}
}

当然，还可以稍微优化一下，即将 end 改为 left ，同时增加一个指针 right：

💡实现思路2

定义一个指针 left ，初始为-1，表示选出最小元素的结束位置。
定义一个指针 right ，初始为size，表示选出最大元素的结束位置。
选择，用一个指针 cur 从left + 1遍历到 right - 1，用两个指针 min、max 记录最小、大值的位置。
- 交换时，如果 left + 1处的值为最大值，即left + 1 == max，交换left + 1与min后，left + 1处变为最小值，min处变为最大值。因此，为了保证交换的正确性，在这种情况下可以让 max = min。
交换，将 left + 1 处的值与 min 处的值交换，将 right - 1 处的值与 max 处的值交换。
left++,right--，继续下一轮。
结束条件为 left >= right ，即所有元素都已排序。

💻代码实现2

void SelectSort2(int* arr, int size)
{
	int left = -1, right = size;
	while (left < right)
	{
		int cur = left + 1;
		int max = cur, min = cur;
		while (cur < right)
		{
			if (arr[cur] > arr[max])max = cur;
			if (arr[cur] < arr[min])min = cur;
			cur++;
		}
		if (max == left + 1)max = min;
		swap(arr[left + 1], arr[min]);
		swap(arr[right - 1], arr[max]);
		left++, right--;
	}
}

2. 🏰 堆排序

堆排序，这个我在数据结构-堆-详解中也讲过.

🖼️示意图

$堆排序 - 示意图$
在这里插入图片描述

📖简介

即使用堆进行排序。

💡实现思路

给一个数组，要使用堆排，前提是必须有个堆，因此第一步为建堆。
那么，建大堆还是小堆？怎么建堆？
建什么堆，这里有个规律：

升序建大堆
降序建小堆

如何建堆，有两种方法：

使用向上调整法，插入建堆
使用向下调整法，调整建堆

建堆
向上调整法：

void HeapSort(int* a, int n)
{
	//建堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}
	//排序
}

向下调整法：
使用向下调整法建堆，需满足左、右子树必须是堆。
随便给的数组肯定不能满足此条件，因此不能从根节点开始建堆，需要找倒数第一个非叶子节点：
在这里插入图片描述
叶节点是堆，空节点也是堆，因此，从第一个非叶子节点开始使用向下调整法，不断调整直到根节点。

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

在实际使用中，通常使用向下调整法建堆，因为向上调整法的时间复杂度为O(N*logN)，而向下调整法的时间复杂度为O(N)。
排序
这里使用的是堆删除的思想来排序。
现在假设排升序，并且已经建好了一个大堆：
在这里插入图片描述

Pop一下，最大的就跑最后去了，然后重复此过程，就能排成升序。
这也验证了：

升序建大堆
降序建小堆

💻代码实现

void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if ((child + 1) < n && a[child] < a[child + 1])
			child++;
		if (a[parent] < a[child])
			Swap(a + parent, a + child);
		else
			break;
		parent = child;
		child = parent * 2 + 1;
	}
}

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

	//排序
	int size = n;
	while (size--)
	{
		Swap(a, a + size);
		AdjustDown(a, size, 0);
	}
}