开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构_排序 -> 正文阅读

[数据结构与算法]数据结构_排序

排序是数据结构中非常重要的内容。排序会涉及到时间复杂度和空间复杂度的计算；排序会运用到数据结构中的基础结构，例如栈、堆等；很多排序算法使用递归会更加容易实现，总之，排序可以说是对数据结构基础内容的综合应用。这篇博客中将会介绍一些常用的排序算法，对于每个算法的复杂度，思路作详细描述。

插入排序

直接插入排序

思想介绍

基本思想：对于一个集合中的元素，顺序地把待排序的元素根据值的大小插入到已排序的序列中。将已排序的元素看成一个子集合，排序刚开始时子集合中只有一个元素，随着排序逐次增大，直到子集合大小和集合大小一致。
举例：假设要对数组a[11] = { 4,7,6,8,2,9,5,3,1,3,10 } 排升序，将数组中的所有元素看成一个集合，初始时子集合就是{ 4 }，4可以看作是有序序列；接下来就是往子集合中插入数据，按照数组中元素的顺序，要把7根据大小插入子集合，插入后子集合变为{4,7}；再接下来要根据大小插入6，插入后子集合变为{4, 6, 7}; …… 依次将未排序的元素都插入到子集合中，这样就和得到按照升序排列的序列。

代码实现

void InsertSort(int* a, int n)
{
	/* 
	   i是有序区间最后一个位置的下标，数组中元素的下标范围是[0，n - 1]
	   所以当i=n-2时说明下次排序是最后一趟排序了，下次排序结束后，数组中所有元素就都有序了，所以结束排序
	*/
	for (int i = 0; i < n - 1; i++)
	{
		int tmp = a[i+1]; // tmp是有序区间后面的第一个位置的元素，就是要插入到有序区间中的数
		int end = i;      // end是有序区间最后一个位置的下标
		
		// 下面这一步是在有序序列中寻找要插入元素位置的过程
		while (end >= 0)  // 插入到有序区间的过程，当end<0时，有序区间的元素已经全部遍历完毕了，所以结束循环
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end]; // 如果tmp<a[end]，那么就把a[end]往后挪
				end--;               // end向前走继续判断
			}
			else
			{
				break;  // 当有序区间中的元素不再大于tmp，跳出循环
			}
		}

		a[end+1] = tmp; // 跳出循环时，tmo要插入的位置肯定是end+1
	}
}

算法性能评价

时间复杂度

最好情况：原始数据已经排好序。此时算法内层的while循环的循环次数每次都是0，外层for循环执行n-1次，for循环内部有3个赋值语句和1个比较语句。因此最好情况下的时间复杂度为 $O (N)$ ;
最坏情况：最坏情况是原始数据的顺序和要排的顺序相反。此时内存while循环每次执行i次，所以for循环中的比较次数和赋值语句的执行次数为等差数列的前n项和，大致是 $n^2$ 量级的。因此最坏情况下的时间复杂度为 $O(N^2)$ .

空间复杂度

直接插入排序的空间复杂度为 $O (1)$

算法稳定性
稳定。
算法稳定性是指排好序的元素之间的相对顺序和原始数据相比保持不变。假设数组a中，a[0]和a[7]中的数值相等，a[0]中的数在a[7]前面，使用某个算法排完序后a[0]中的数还在a[7]前面，这就说明该算法是稳定的，否则就是不稳定的。

希尔排序

希尔排序又称为缩小增量排序。增量指的是原始数据分成的小组中元素的个数。

思想介绍

直接插入排序的时间复杂度在 $O (N)$ 和 $O(N^2)$ 之间，原始数据越接近有序，直接插入排序的时间效率就越高，希尔排序就是利用这一点提出的。

基本思想：把待排序的数据元素分成若干个小组，对同一小组的内的数据元素
用直接插入排序；小组的个数逐次减少，当所有数据都在同一小组内排序后，排序过程结束。
解释：分成多个小组之后小组内的数据元素更少，然后对小组内的元素使用插入排序，使得小组内的数据有序，这样做是因为小数目数据使用插入排序需要移动的数据更少；然后减少小组的个数，进行直接插入排序，直到所有数据元素都在同一个小组，最后使用直接插入排序。这样做的时间复杂度是优于直接使用插入排序的。

代码实现

void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{
		gap = (gap / 3) + 1;

		// 先写插入排序
		// 与普通的插入排序的区别是：间隔不再是固定的1，而是变化的gap，初始gap较大，相当于预排序，当gap变为1时，就是普通插入排序了
		for (int i = 0; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[i + gap];

			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

算法性能评价

时间复杂度

希尔排序的时间复杂度会收到gap取值的影响，根据上述代码中的gap取值方式，时间复杂度应该在 $O(N^1.25)$ 和 $O(1.6\times N^1.25)$ 之间。

空间复杂度

希尔排序的空间复杂度为 $O (1)$

算法稳定性

不稳定。分组排序时可能会打乱很多元素的相对位置。

选择排序

直接选择排序

一般情况下，选择排序就是指直接选择排序。

思想介绍

基本思想：每次从待排序的数据元素中集合中选取值最小的元素，放到数据元素集合最前面（或最后面），数据元素集合不断缩小，当数据元素集合为空时，排序结束。
实现方式：排升序时，每次从待排序的数据元素集合中选取最小的数放在数据元素集合最前面，最大的数放在最后面。

代码实现

void SelectSort(int* a, int n)
{
	int left = 0; 
	int right = n - 1;

	while (left < right)
	{
		int MinIndex = left, MaxIndex = left;

		for (int i = left; i <= right; i++)
		{
			if (a[i] < a[MinIndex])
			{
				MinIndex = i;
			}

			if (a[i] > a[MaxIndex])
			{
				MaxIndex = i;
			}
		}
		// 把待排序的数中的最小数交换到数据元素集合最前面
		Swap(&a[left], &a[MinIndex]);

		// 判断数据元素集合最前面的数是否是最大的数，如果是的话，这个数肯定就被交换到最小的数的位置了，所以最大数的下标变成了交换前最小数的下标
		if (MaxIndex == left)
		{
			MaxIndex = MinIndex;
		}
		// 把待排序的数中的最大数交换到数据元素集合最后面
		Swap(&a[MaxIndex], &a[right]);

		left++;
		right--;
	}
}

算法性能评价

时间复杂度

直接选择排序算法最外层while循环大概会执行n/2次，内层for循环大概执行n+(n-2)+ … +0次，循环内部的赋值语句和比较语句都是常数个，所以总的时间复杂度应该是 $O(N^2)$ .

空间复杂度

直接选择排序不需要额外开辟空间，所以空间复杂度为 $O (1)$ .

算法稳定性

稳定。在待排序的数据元素集合中选择最小或者最大的时候，选择的是遇到的第一个最小的数或者最大的数，因此不会打乱数据元素的相对位置。

堆排序

堆排序也是选择排序的一种。

思想介绍

基本思想：排升序建大堆，排降序建小堆。每次选择堆中根结点位置的元素放到待排序元素集合的最后一个位置。

堆排序分为建堆过程和排序过程，向下调整算法是核心。

代码实现

void AdjustDwon(int* a, int n, int root)
{
	int child = root * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}

		if (a[child] > a[root])
		{
			Swap(&a[child], &a[root]);

			root = child;
			child = root * 2 + 1;
		}
		else
		{
			// 如果在调整完毕后不跳出，那么程序将陷入死循环
			break; // break很重要，但是写代码时容易遗漏，需要注意
		}

	}
}

void HeapSort(int* a, int n)
{
	// 建堆过程
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}
	
	// 排序过程
	for (int i = n-1; i > 0; i--)
	{
		Swap(&a[i], &a[0]);

		AdjustDwon(a, i, 0);
	}
}

算法性能评价

时间复杂度

使用向下调整算法建堆的时间复杂度
堆是完全二叉树，为了方便计算，我们直接计算跟堆层数相等的满二叉树建堆的时间复杂度。在最坏的情况下，满二叉树中所有非叶结点都要使用向下调整算法来调整，假设树的高度为 $h$ ，那么第 $1$ 层有 $2^0$ 个结点，需要向下移动 $h ? 1$ 层；第 $2$ 层有 $2^1$ 个结点，每个结点需要向下移动 $h ? 2$ 层；以此类推第 $h ? 1$ 层有 $2^h-2$ 个几点，每个结点需要向下移动 $1$ 层；那么总的移动次数为：
$T(n)=2^0\times (h-1)+2^1\times (h-2)+2^2\times (h-3)+...+2^{h-2}\times 1$
对于上式可以采用错位相减法计算：
$\begin{aligned} 2\times T(n)-T(n)&=2^1+2^2+ ....+2^{h-2}+2^{h-1}-2^0\times (h-1)\\ &=\frac {2(1-2^{h-1})} {1-2}-h+1\\ &=2^h-h-1. \end{aligned}$
根据满二叉树结点个数和树的深度关系 $2^h-1=N$ 可得
$T(N) = N-Log_2N$
用大O表示法可得建堆的时间复杂度为 $O (N)$
排序过程的时间复杂度
每次交换根结点元素和最后一个位置的元素，交换完之后再调整堆，假设待排序元素个数为N，第一次排序后需要调整 $Log_2{(N-1)}$ 次，第二次排序后要调整 $Log_2{(N-2)}$ 次，…，最后一次排序后要调整0次，则一共需要调整的次数为
$Log_2(N-1) + Log_2(N-2) +...+Log_2(1) = Log_2(n-1)!\leq N\times Log_2N$
用大O表示法为 $O(N\times Log_2N)$

综上堆排序的时间复杂度为 $O(N\times Log_2N+N)=O(NLog_2N)$

空间复杂度
堆排序的空间复杂度为 $O (1)$

算法稳定性
堆排序过程中会打乱原始数据的顺序，所以堆排序是不稳定的。

交换排序

冒泡排序

思想介绍

基本思想：设数组a中存放了n个数据元素，循环进行n-1趟如下排序：从a[0]开始依次比较相邻两个数的值，如果逆序就交换，否则不交换。这样的话第1趟排序结束后，数值最大的数据元素就会被放在a[n-1]中；第2趟结束后次大的数会被放到a[n-2]中；n-1趟结束之后序列就有序了。

代码实现

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}

算法性能评价

时间复杂度
$O(N^2)$

空间复杂度
$O (1)$

算法稳定性
稳定

快速排序

思想介绍

基本思想
递归法：假设待排序的数据元素存放在数组a中，选取最左边的数据元素a[0]作为关键值key，然后从待排序数据元素左边left和右边right开始(left和right指数组下标，初始时left=0，right=n-1)，先从右边往左遍历找比key值小的数据元素low，然后从左边往右边遍历找比key值大的数据元素high，找到后交换low和high；然后接着找，直到left大于或等于right，这时候交换key和a[left]，此时，key左边的数都比key小，右边都比key大，然后按照上面的思路递归对key的左右两边区间进行排序。
概括解释：快排简单来说就是，在要排序的数据中选取一个基本值，将这个基本值放到属于它的位置上（排好序时它的位置），然后这个值的左边都是小于它的数，右边都是大于它的数；接下来对于这个基本值左右两边的区间采用同样的思路进行排序，然后一直递归，直到区间中的数据个数为1，此时整个序列就有序了。

非递归法：利用栈来实现。将要排序的区间左右下标依次入栈，然后出栈，找到基本值的位置，如果基本值左右两边区间依旧存在，那么将左右两边区间边界下标依次入栈，然后再出栈，一直重复这个过程直到左右区间不存在。

要点

确定基本值：我们期望我们选择的基本值是中位数，这样的话基本值处于序列中间，可以将原数组均分为两个子数组，递归总次数为 $Log_2N$ 量级;否则，如果我们选取的基本值在序列左边或者右边，那么递归总次数就是 $N^2$ 量级。所以对于基本值的选取，我们采用三数取中法来实现。
确定基本值的位置：对于快排来说，找到基本值的位置是最关键的，这个步骤一共有三种方法来寻找。

上面两个要点将在代码中体现：三数取中由函数GetMidIndex实现，确定基本值得位置分别用PartSort1、PartSort2和PartSort3实现。

代码实现

递归法

// 在a[mid],a[left],a[right]中选择中间的数。三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;

	if (a[mid] < a[right])
	{
		if (a[mid] > a[left])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[right] > a[left])
		{
			return right;
		}
		else if (a[left] > a[mid])
		{
			return mid;
		}
		else
		{
			return left;
		}
	}
}

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	int keyi = left;

	// 三数取中是为了防止要排的数是逆序的，如果是逆序，没有三数区中会导致相遇坐标都在数组两端，递归次数最大。
	int MidIndex = GetMidIndex(a, left, right); 
	Swap(&a[left], &a[MidIndex]);

	while (left < right)
	{
		// 找小-找到比keyi位置更小的数停下
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}

		// 找大-找到比keyi位置更大的数停下
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		
		// 交换小的和大的，实现将小于a[keyi]放到左边，大的放到右边
		Swap(&a[left], &a[right]);
	}

	// 将a[keyi]放到两段区间中间
	Swap(&a[keyi], &a[left]);

	return left;
}

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int MidIndex = GetMidIndex(a, left, right);
	Swap(&a[MidIndex], &a[left]);

	int key = a[left]; // left就相当于是挖的坑

	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}

		// 将a[right]放到a[left]中, right就是挖的坑
		a[left] = a[right];

		while (left < right && a[left] <= key)
		{
			left++;
		}

		a[right] = a[left];
	}

	a[left] = key;

	return left;

}

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int prev = keyi;
	int cur = prev + 1;

	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			if (prev != cur)
			{
				Swap(&a[prev], &a[cur]);
			}
		}

		cur++;

	}

	Swap(&a[keyi], &a[prev]);

	return prev;

}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	// 确定相遇点，对于相遇点两边的数据进行递归排序
	int meeti = PartSort1(a, left, right);

	QuickSort(a, left, meeti - 1);
	QuickSort(a, meeti + 1, right);

}

非递归法

#include"Stack.h"

// 快速排序 非递归实现-栈
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);

	StackPush(&st, left);
	StackPush(&st, right);

	while (!StackEmpty(&st))
	{
		// 下面几行代码是利用栈，来选择择要排序的区间
		int left, right;

		right = StackTop(&st);
		StackPop(&st);

		left = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort1(a, left, right); 

		if (left < keyi - 1) // 如果成立说明相遇点左边还有没排序的区间
		{
			StackPush(&st, left); // 先让左边界入栈
			StackPush(&st, keyi - 1); // 再让右边界入栈
		}

		if (right > keyi + 1) // 如果成立说明相遇点右边还有没排序的区间
		{
			StackPush(&st, keyi + 1); // 先让左边界入栈
			StackPush(&st, right); // 再让右边界入栈
		}
	}
}

算法性能评价

时间复杂度
$O(NLog_2N)$ 。主要是算递归的次数。

空间复杂度
$O(Log_2N)$ (不同写法可能会不一样)

算法稳定性
不稳定

归并排序

思想介绍

基本思想：设数组a中存放了n个数据元素，初始时把它们看成n个长度为1的有序子数组，然后从第一个有序子数组开始，把相邻的有序子数组两两合并，得到[n/2]个长度为2的新的有序数组(n为奇数时，最后一个新的有序子数组的长度为1)。对这些新的有序子数组在进行两两归并。如此重复直到得到一个长度为n的有序数组为止。

代码实现

void _mergeSort(int* a, int left, int right, int* tmp)
{
	// 递归结束条件，左边界大于等于右边界，此时区间中肯定最多只有一个数据了
	if (left >= right)
	{
		return;
	}

	int mid = (left + right) >> 1; // 相当于除以2

	// 归并的前提是分割到最小区间，然后慢慢往回归并
	// 先将[left,right]分割为：[left,mid]和[mid+1,right]，然后这两个区间继续细分为两个区间，直到分成只有一个数的区间
	_mergeSort(a, left, mid, tmp);
	_mergeSort(a, mid + 1, right, tmp);

	// 分割完毕后开始归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	for (int j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
}

void MergeSort(int* a, int n)
{
	// 归并过程需要用到额外的空间，所以首先开辟一个跟原数组大小相同的空间
	int* tmp = (int*)malloc(sizeof(int) * n);

	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	_mergeSort(a, 0, n - 1, tmp);

	free(tmp);
}

此外，归并排序还有非递归实现方法，代码如下：

void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
	// 归并过程
	int left = begin1;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	for (int j = left; j <= end2; j++)
	{
		a[j] = tmp[j];
	}
}

void MergeSortNonR(int* a, int n)
{
	// 跟普通归并一样，首先需要开辟额外的空间
	int* tmp = (int*)malloc(sizeof(int) * n);

	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	// 接下来确定归并的区间
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			// 判断第二个区间是否存在，若是不存在则说明不需要再归并了
			if (begin2 >= n)
				break;
			// 如果走到这说明第二个区间左边界在数组下标范围内，但是右边界超出范围了，所以
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			// 根据区间归并,这是一个迭代过程
			_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);
		}

		gap *= 2;
	}

	free(tmp);
}

算法性能评价

时间复杂度
$O(NLog_2N)$

空间复杂度
$O (N)$

算法稳定性
稳定。

非比较排序

计数排序

思想介绍

基本思想：对于待排序的一组数，统计这组数所处在的区间和相同的数出现次数，然后根据统计结果将数按照顺序放回原数组中。

下图是对计数排序算法的形象展示
在这里插入图片描述

解释
我把统计待排序数据相同元素个数的数组称为统计数组，
$统计数组大小 = ma x ? min + 1$
上图中max=19,min=11,所以统计数组大小为19-11+1=9，开辟一个大小为9的数组a，a[0]位置存11的个数，a[1]位置存12的个数，… ，a[8]位置存19的个数，上图中元素和它的个数按照颜色对应。

代码实现

void CountSort(int* a, int n)
{
	// 第一步：找出这组数中的最大、最小值
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];

		if (a[i] < min)
			min = a[i];
	}

	// 第二步：统计数组中数据的多样性（等于统计数组的大小），然后统计每个类别数据的个数
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range); // 对开辟的空间赋值为0

	for (int i = 0; i < range; i++)
	{
		count[a[i] - min]++; // 统计每个类别的数的个数
	}
	
	// 第三步：对原数组赋值,把count数组中的数全赋给a
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
	
	free(count);
}