算法 -排序 -插入,选择

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

💡插入排序

插入排序可以分为直接插入排序和希尔排序。

1. ➡️直接插入排序

📖简介

直接插入排序常用于处理数据量较小的情况，其思想和打牌类似，都是将新元素插入到有序数组。
时间复杂度为 $O(N^2)$ 。如果数据量过大，直接插入排序会因频繁的挪动数据降低效率。

💡实现思路

实现的思路：

• 定义一个指针 end ，初始为0，表示已排序数组的结束位置。
• 取牌，用一个临时变量 tmp 存储 end + 1处的值，表示待插入的值。
• 挪牌，将已排序的数组中小于 tmp 的向后挪动一个位置。（这里 end + 1 的值已被保存，可以直接覆盖）
  • 定义 cur 指向 end。
  • 如果 cur 处的值大于 tmp，将该值向后挪动一位，然后cur--。
  • 结束条件为 cur <= -1 或者 cur 处的值小于等于 tmp。
• 插入，将 tmp 插入 cur + 1处，然后 end++。
• 结束条件为 end >= size - 1 ，即所有元素都已排序。

📝具体示例

下面是具体示例：
待排序数组：

首先，定义一个指针 end ，指向 0 处，表示已排序手牌：

取牌，用一个临时变量 tmp 存储 end + 1处的值，表示待插入的手牌：

挪牌：(当cur == -1，停止挪牌)

插入：(将tmp插入cur + 1处)

第二轮取牌加挪牌：（当cur处的值小于 tmp，也停止挪牌）

插入：

之后，重复上述过程即可。

🖼️示意图

$$插入排序-示意图$$

)

💻代码实现

最后是代码实现：

void InsertSort(int* arr, int size)
{
	int end = 0;
	while (end != size - 1)
	{
		int tmp = arr[end + 1];
		int cur = end;
		while (cur > -1 && arr[cur] > tmp)
		{
			arr[cur + 1] = arr[cur];
			cur--;
		}
		arr[cur + 1] = tmp;
		end++;
	}
}

2. ⬆️希尔排序

📖简介

希尔排序是插入排序的升级版，本质是通过分组进行插入排序，可以将较大的数据尽快的挪到数组后面，从而减少挪动数据的次数，提高了效率。
时间复杂度大约为 O(N ^ 1.3)，具体时间复杂度会随分组的标准而变。

💡实现思路

实现的思路：

• 定义 gap ，初始值为 size/3 + 1，间隔为 gap 的数被分到一组。
• 对每组进行插入排序
  • 定义一个指针 end ，初始为0，表示已排序数组的结束位置。
  • 取牌，用一个临时变量 tmp 存储 end + gap处的值，表示待插入的值。
  • 挪牌，将已排序的数组中小于 tmp 的向后挪动一个位置。（这里 end + gap 的值已被保存，可以直接覆盖）
    • 定义 cur 指向 end。
    • 如果 cur 处的值大于 tmp，将该值向后挪动一位，然后cur -= gap。
    • 结束条件为 cur <= -1 或者 cur 处的值小于等于 tmp。
  • 插入，将 tmp 插入 cur + gap处，然后 end++。
  • 结束条件为 end >= size - gap ，即所有元素都已排序。
• gap = gap/3 + 1
• gap == 1 为最后一次排序，此时变为直接插入排序。（经过了预处理，此时的直接插入排序效率大大提高）

🖼️示意图

$$希尔排序-示意图$$

💻代码实现

下面是代码实现：

void ShellSort(int* arr, int size)
{
	int gap = size;
	while (gap != 1)
	{
		gap = gap / 3 + 1;
		int end = 0;
		while (end < size - gap)
		{
			int tmp = arr[end + gap];
			int cur = end;
			while (cur > -1 && arr[cur] > tmp)
			{
				arr[cur + gap] = arr[cur];
				cur -= gap;
			}
			arr[cur + gap] = tmp;
			end++;
		}
	}
}

💡选择排序

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

1. 🔄选择排序

📖简介

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

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

💡实现思路

实现的思路：

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

• 定义一个指针 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 ，即所有元素都已排序。

下面是代码实现：

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. 🏰堆排序

堆排序，这个我在数据结构-堆-详解中讲过了，此处略。

🖼️示意图

$$堆排序-示意图$$

希望本篇文章对你有所帮助！并激发你进一步探索编程的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！