带你学懂数据结构中的八大排序（上）

北海

发布于 2023-07-01 11:35:15

2610

📘前言

排序（Sort）是初阶数据结构中的最后一块内容，所谓排序，就是通过某种手段，使目标数据变为递增或递减，排序有很多种方式：插入、选择、交换、归并、映射等等，本文会介绍这些方式下的详细实现方法，因篇幅较长，故分为上下文的形式介绍，本文是上半部分。

下面是通过排序生成的排行榜

📘正文

📖插入排序

插入，指将数据插入到合适位置，这个分类中包含了两种排序算法：直接插入与希尔，其中希尔排序又称缩小增量排序，是一种非常快但不稳定的排序，它的时间复杂度计算极为复杂，下面详细来看看这两个排序吧

📃直接插入排序

思路：从第二个数开始，假设此数为 tmp ，逐个往前进行比对，如果前数大于 tmp ，就将前数值赋值到 tmp 处，然后继续往前比对，直到找到小于或等于 tmp 的数（或者比对至数据首）就停止，最后将 tmp 的值赋值到此处就行了

//直接插入排序
void InsertSort(int* pa, int n)
{
	assert(pa);

	//从后往前比较，找到合适位置就插入
	for (int i = 1; i < n; i++)
	{
		int end = i;
		int tmp = pa[end];
		while (end)
		{
			if (pa[end - 1] > tmp)
				pa[end] = pa[end - 1];
			else
				break;
			end--;
		}
		pa[end] = tmp;
	}
}

动图展示

时间复杂度：

最坏：数据为一个逆序的等差数列 O(N^2)
最好：顺序有序 O(N)

空间复杂度：

仅仅只需要一个 tmp 变量 O(1)

稳定性：

稳定，当两个相同数相遇时，后者是不会跑到前者前面去的

📃希尔排序

希尔排序是在直接插入排序上进行优化的一种排序，希尔排序分为两步：

1、预排序，使得数据尽可能接近有序
2、直接插入排序，最后调用一次直接插入排序，快速的完成排序

思路：预排序是通过区间划分实现的，假设当前区间为 gap，那么 1、1+gap*n 可以分成一组，同理2、3、4 都可以分，将这些组分别进行直接插入排序（数据少，效率高）。每完成一次分组排序，gap 就会缩小，直到 gap 为1时，进行一次直接插入排序，整个希尔排序就完成了

//希尔排序
void ShellSort(int* pa, int n)
{
	assert(pa);

	//思路：在插入排序的基础上，先分为n个区间，使数组尽可能有序（预排序）
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;	//确保gap最后为1
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = pa[end + gap];
			while (end >= 0)
			{
				//此时的end位于tmp之前s
				if (pa[end] > tmp)
					pa[end + gap] = pa[end];
				else
					break;

				end -= gap;
			}

			pa[end + gap] = tmp;
		}
	}
}

动图展示（图太长了，分段展示） 1、预排序

2、直接插入排序

时间复杂度：

希尔的时间复杂度计算是一个极其复杂的过程，需要用到高等数学的知识，这里直接记就行 O(N^1.3)

空间复杂度：

仅仅只需要一个 tmp 变量 O(1)

稳定性：

不稳定，当两个相同数被不同区间选中时，可能会发生交换现象，示例 1 4 2 2 3

📖选择排序

选择排序下也可以分为两种：简单选择与之前学过的堆排序，两者的本质是一样的，都是依赖于不断的比对，选到合适数后进行交换

📃简单选择排序

思路：选到最大的数，然后与 end 值交换；优化：选最大与最小，分别与 end 值和 begin 值交换

void swap(int*pnum1, int* pnum2)
{
	assert(pnum1 && pnum2);

	int tmp = *pnum1;
	*pnum1 = *pnum2;
	*pnum2 = tmp;
}

//简单选择排序
void SelectSort(int* pa, int n)
{
	assert(pa);

	//思路：选最小的放前面，选最大的放后面
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;

		for (int i = begin + 1; i <= end; i++)
		{
			if (pa[i] > pa[maxi])
				maxi = i;
			if (pa[i] < pa[mini])
				mini = i;
		}
		swap(&pa[begin], &pa[mini]);
		if (maxi == begin)
			maxi = mini;

		swap(&pa[end], &pa[maxi]);

		begin++, end--;
	}
}

动图展示：

时间复杂度：

这是一个比较糟糕的排序，因为不管是什么情况都是 O(N^2)

空间复杂度：

仅借助变量辅助交换 O(1)

稳定性：

不稳定，在选择时，可能把相同数中的后者选到前面，示例 1 4 2 2 3

注意：

当交换 min 值与 begin 值后，如果 max 等于此时的 begin ，那么就要将 max 赋为 min，即 max = min

📃堆排序

思路：堆排序用到了堆的知识，如果想排升序的话建大堆，因为大堆中堆顶是最大值，将堆顶值与堆低值交换后，执行向下调整，使其再次变为大堆，就这样反复交换、调整，堆排序就完成了

void swap(int*pnum1, int* pnum2)
{
	assert(pnum1 && pnum2);

	int tmp = *pnum1;
	*pnum1 = *pnum2;
	*pnum2 = tmp;
}

void AdjustDown(int* pa, int n, int parent)
{
	assert(pa);

	//大堆，找大孩子，调整
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && pa[child + 1] > pa[child])
			child++;

		if (pa[child] > pa[parent])
		{
			swap(&pa[child], &pa[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

//堆排序
void HeapSort(int* pa, int n)
{
	assert(pa);

	//思路：升序建大堆，将堆顶元素沉底，然后再调整
	int parent = (n - 1 - 1) / 2;	//找父亲
	for (int i = parent; i >= 0; i--)
		AdjustDown(pa, n, i);

	//将堆顶元素沉底后调整
	int end = n - 1;
	while (end > 0)
	{
		swap(&pa[0], &pa[end]);
		AdjustDown(pa, end--, 0);
	}
}