【数据结构】插入排序、选择排序、冒泡排序、希尔排序、堆排序

前言：生活中我们总是会碰到各种各样的排序，今天我们就对部分常用的排序进行总结和学习，今天的内容还是相对比较简单的一部分，各位一起加油哦！

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！

---

插入排序

插入排序：我们可以通俗的理解成将一个数记录下来按其数值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。(由于动图画的实在太过于繁琐博主就画了一半，请见谅)

代码思路：由此图我们可以知道，我们用一个tmp记录后面一个元素，如果后面的比前面的小，就让前面的元素逐一和他比较并往后走，如果碰到比他小的就停下来插入到此位置。（不理解的话可以理解成我们平常玩的斗地主的牌，拿一张牌插到应该有的位置）。

---

代码实现：

void InsertSort(int* a, int n)//插入排序
{
	for (int i = 0; i < n - 1; i++)//升序
	{
		int end = i;
		int tmp = a[end + 1];//保存后一个
		while (end >= 0)
		{
			if (tmp < a[end])//前一个大于后一个,让大的全部往后走
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;	
			}
		}
		a[end + 1] = tmp;//在把小的放在此时的位置
	}
}

测试函数:

void Test_InsertSort()
{
	int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };
	InsertSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}

排序结果:

---

希尔排序

希尔排序:我们可以通俗的把待排的序列看成若干个子序列，然后对其分别进行直接插入排序，最后在对全部进行一次排序即可。(如下图所示)

---

我们可以理解成gap>1是预排序，目的是让它接近有序
gap == 1是直接插入排序，目的是让它有序。但是记住最后一定要让gap最后一次排序为1。
代码思路:我们可以把每次排序写成一次插入排序，然后最后一让其间距不断的变化直到最后一次全部排序完成。
代码实现:

void ShellSort(int* a, int n)//希尔排序 
{
	int gap = n;
	while (gap)
	{
		gap = gap / 2 ;
		for (int i = 0; i < n - gap; i++)//升序
		{
			int end = i;
			int tmp = a[end + gap];//保存后一个
			while (end >= 0)
			{
				if (tmp < a[end])//前一个大于后一个,让大的全部往后走
				{
					a[end + gap] = a[end];
					end = end -gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;//在把小的放在此时的位置
		}
	}
}

---

函数测试

void Test_ShellSort()
{
	int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}

运行结果:

---

冒泡排序

冒泡排序：也是我们所碰到的最简单的一种排序，这种排序的思想是十分简单的，我们可以理解成每一趟找到序列中最大的一个或最小的元素，排序到序列的最左边(右边)，然后排序序列的有效次数趟即可排序完成(如下图)。

代码实现:

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void BubbleSort(int* a, int n)//冒泡排序
{
	int i = 0;
	for (int j = 0; j < n - 1; j++)
	{
		for (i = 0; i < n - j -1; i++)//每一趟找到一个最大的
		{
			if (a[i] < a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
	}
}

---

函数测试:

void Test_BubbleSort()
{
	int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };
	BubbleSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}

运行结果

---

选择排序

选择排序：我们现在一组有序序列中找到最大(最小)和第一个位置交换，然后再找次大的和第二个交换以此类推，最后我们即可得到一个有序序列。（如下图所示）

---

代码实现：

void SelectSort(int*a ,int n)//选择排序
{
	//现在数组中找到最小的，然后和第一个位置交换
	//再找到次小的，和第二个位置交换
	int min = 0;
	for (int i = 0; i < n - 1 ; i++)
	{
		min = i;//最小的数的下标
		for (int j = i; j < n; j++)
		{
			if (a[min] > a[j])//找到最小位置的下标
			{
				min = j;
			}
		}
		if(min != i)
			Swap(&a[i], &a[min]);
	}
}

---

测试函数

void Test_SelectSort()
{
	//int a[] = { 1,2,30,0,99,1,7,8,2,11,0,3,13 };
	int a[] = { 1,0,0,0,99,1,7,8,2,9,0,3,0 };

	SelectSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));

}

运行结果:

---

但是上面这种方法我们一共要找n-1次，我们思考一下每一次查找的过程中，如果我们每次一起查找最大的和最小的，那我们不就提高了一倍的效率。所以我们只需要再引入一个max变量来帮助我们再记录一下这个值即可。
代码实现：

void SelectSort_best(int* a, int n)//选择排序
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int max = begin;
		int min = begin;
		int i = 0;
		for (i = begin + 1; i <= end; i++)//找最小的和最大的
		{
			if (a[i] < a[min])
			{
				min = i;
			}
			if (a[i] > a[max])
			{
				max = i;
			}
		}
		Swap(&a[begin], &a[min]);
		if (begin == max)//防止最大的和最小的是相同的
		{
			max = min;
		}
		Swap(&a[end], &a[max]);
		begin++;
		end--;
	}
}

运行结果依然和前面的相同，这里就不做更多的阐述了。

---

堆排序

堆排序：前面我们讲了堆的模拟实现，我们知道堆的父亲结点一定比它的孩子结点大(小)，因此我们可以充分的利用这一点来进行排序。

1. 首先我们们将数组中的元素，想象成一个堆，将其中的父亲结点全部向下调整。（如下图）
2. 根据我们模拟建立的大堆或者小堆，将其堆顶元素和堆尾进行交换，因此我们可以得到一个最大(最小的元素)再堆底，然后再通过一个end记录尾部，交换一次减减一次，以此循环到end为0的时候即堆中所有元素也排序完成。(如下图所示)
   

---

代码实现:

void AdjustDown(int* a, int size, int parent)//向下调整
{
	assert(a);
	int child = parent * 2 + 1;//找到第一个孩子
	while (child < size)
	{
		//看俩个孩子谁更小，交小的那个与父亲去比较
		if (a[child] < a[child + 1] && (child + 1) < size)
		{
			child += 1;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;//让父亲和儿子往下走
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)//堆排序
{
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)//建堆,只有父亲结点需要调整
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

---

函数测试:

void Test_HeapSort()
{
	int a[] = { 20,10,8,2,1,2,7 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}

运行结果:

---

好啦，今天的内容就到这里啦，下期内容预告【快速排序的模拟实现】-- 四种方式

---

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

---

🫵🫵🫵 祝各位接下来好运连连 💞