常见排序算法及其稳定性分析

前言：

排序算法可以说是每一个程序员在学习数据结构和算法时必须要掌握的知识点，同样也是面试过程中可能会遇到的问题，在早些年甚至还会考冒泡排序。由此可见呢，掌握一些常见的排序算法是一个程序员的基本素养。虽然现在的语言标准库里都有直接的排序函数，但是作为一个学习者，我们应当抱着“知其然，还要知其所以然”的态度去学习。

1.常见的排序算法有哪些？

常见的排序算法及其性能：

算法名称	平均时间复杂度	稳定性
直接插入排序	N^2	稳定
希尔排序	N^1.25--1.6N^1.25	不稳定
选择排序	N^2	不稳定
堆排序	NlogN	不稳定
冒泡排序	N^2	稳定
快速排序	NlogN	不稳定
归并排序	NlogN	稳定

这里呢我只讲一些效率比较高的排序算法，比如快排、并排、堆排序、希尔排序。

2.常见排序算法的实现

2.1希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成grap个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序（插入排序）。然后，重复上述分组和排序的工作。当分组间距为1时，所有记录在统一组内排好序。

?

代码实现：

// 希尔排序
void ShellSort(int* a, int n) {
	int gap = n - 1;//grap为分组之间的间隔
	while (gap > 1) {
		gap = gap / 3 + 1;//每次分组的间距都越来越小，直到间距为一
		for (int i = 0; i < gap; i++) {//i表示每组的开头位置
			for (int j = i; j < n - gap; j += gap) {//对每一组插入排序
				int end = j;
				int temp = a[j + gap];
				while (end >= 0) {
					if (temp < a[end]) {
						a[end + gap] = a[end];
						end -= gap;
					}
					else {
						break;
					}
				}
				a[end + gap] = temp;
			}
		}
	}
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时（相当于对整个数组进行插入排序），数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好多书中给出的 希尔排序的时间复杂度都不固定，目前也只能给出一个大概的复杂度。

2.2堆排序

关于堆排序在之前的博客中已经详细讲解过，有兴趣的可以去看看。

解决top-k问题--堆排序-CSDN博客文章浏览阅读140次，点赞8次，收藏5次。堆排序将堆的根节点与最后一个节点交换，然后将堆的大小减1，并进行堆的重构。max1>max2,a[i]>max2,所以此时的max2的值已经不是这个数组次大的了。被淘汰说明有前k个数大于自己，加入top-k说明此时的a[i]至少大于目前的maxk。，如果大于此时的maxk,说明就目前来说，a[i]有资格进入这前k大的数，通常的做法是用一个变量max1依次去比较数组中的每一个数，并更新。，它的每个节点的值都大于等于（或小于等于）它的子节点的值。先把此时的maxk的值去掉，算上a[i]之后调整这k个数。https://blog.csdn.net/qq_62987647/article/details/134765613

?2.3快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

?2.3.1递归版

对于单趟排序，我们确定一个基准值key,并利用双指针从首尾两端移动。找到一个位置放key，使得，key左边的元素都小于key(以升序排序为例)，右边的元素都大于key。

快排的算法思想本质是用空间换取时间，每一次递归排序的区间都在不断地缩小，每一趟排序都确定了下一趟排序的左右两个区间，类似于二叉树的节点的左右儿子节点。?

代码实现

int PartSort1(int* a, int left, int right) {//单趟排序
	int end = right;
	int begin = left;
	int mid = GetMid(a, left, right);//基准值的下标
	Swap(&a[left], &a[mid]);//跟首元素交换
	int key = left;
	while (begin < end) {
		while (end > begin && a[end] >= a[key])end--;
		while (end > begin && a[begin] <= a[key])begin++;
		Swap(&a[end], &a[begin]);
	}
	Swap(&a[key], &a[begin]);
	return begin;//单趟排序后返回最后key所处的位置
}
void QuickSort(int* a, int left, int right){//递归
	   if (left >= right)return;
	    int mid = PartSort3(a, left, right);
		QuickSort(a, left, mid - 1);
		QuickSort(a, mid + 1, right);
}

?2.3.2非递归版

利用栈，我们可以将单趟排序确定的两个子区间存起来，模拟函数栈帧的开辟。这样一来，我们就可以不用递归（递归较为耗损空间）就可以完成快速排序。

如果有对函数栈帧不了解的朋友可以去我之前写的博客里面看看。

深入理解函数调用--函数栈帧-CSDN博客文章浏览阅读87次，点赞6次，收藏3次。寄存器：寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。函数栈帧（Function Stack Frame）是在程序执行过程中，用来保存函数调用信息和局部变量的数据结构。它包含了函数的参数、返回地址和局部变量等信息。通俗的来说，就是在调用函数的时候系统给你开辟在栈区的一部分空间，专门用来存放局部变量等。https://blog.csdn.net/qq_62987647/article/details/132663764代码实现

void QuickSortNonR(int* a, int left, int right) {
	Stack ST;
	StackInit(&ST);
	StackPush(&ST, right);//根据栈的特性，先将右区间压栈
	StackPush(&ST, left);
	while (!StackEmpty(&ST)) {
		int l = StackTop(&ST);
		StackPop(&ST);
		int r = StackTop(&ST);
		StackPop(&ST);//取出一个区间[l,r]
		if (l > r)Swap(&l, &r);
		int keyi = PartSort1(a, l, r);//单趟排序
		if (keyi -1> l) {
			StackPush(&ST, keyi - 1);
			StackPush(&ST, l);
		}
		if (keyi + 1 < r) {
			StackPush(&ST, r);
			StackPush(&ST, keyi + 1);
		}
	}
	StackDestroy(&ST);
}

?2.4归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。?与快排不同的是，归并排序是先递归后排序。

实现思路：?

因为要先满足每个子序列都有序的条件，我们可以把区间长度划分为1，这样每个区间都一定是有序的，再对每个区间先上合并。值得注意的是，有序地子区间合并之后也是有序的。同样是根据二叉树的思想，每个区间一分为两个子区间，直到区间长度为1，需要logN的时间复杂度，合并两个区间又是N的复杂度，所以总的时间复杂度为NlogN。

?代码实现

void MergeSort(int* a, int begin, int end, int* temp) {//temp用于暂时存放合并后的数组
	if (begin >= end)return;
	int mid = (begin + end) / 2;
	MergeSort(a, begin, mid, temp);
	MergeSort(a, mid + 1, end, temp);//先递归区间
	
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;//两个区间的端点指针
	int i = begin;//合并数组的下标的指针
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {//比较两个区间的首元素，小的放入temp中，两个指针往后移
			temp[i++] = a[begin1++];
		}
		else {
			temp[i++] = a[begin2++];
		}
	}//有可能还有某个区间还有元素没有放进去
	while (begin1 <= end1) {
		temp[i++] = a[begin1++];
	}
	while (begin2 <= end2) {
		temp[i++] = a[begin2++];
	}
	//将合并好的数组复制到原数组中
	memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}

3.排序算法的稳定性

对于某种排序算法，如果会将两个相同大小的元素的相对位置改变，那么我们就称这个算法是不稳定的，否者就是稳定的。?

什么时候需要考虑稳定性？

针对多个字段进行排序，就可能需要考虑排序算法的稳定性

?举例：

对以下数据进行排序：

序号	订单金额	订单时间
1	50	9：04
2	30	9：00
3	50	9：03
4	10	9：01

要求：

是按照订单金额进行升序排序，如果订单金额相同，则按照下单时间升序排序

先按照订单时间升序排序得到序号为：2、4、3、1

再从上一个序号组中按照订单金额升序排序

1.假如排序算法不稳定

则可能得到：4、2、1、3

对于序号1和3，订单金额相同，但是时间小的反而排在后面，不符合要求。

2.假如排序算法稳定

则一定得到：4、2、3、1

对于序号1和3，订单金额相同，下单时间大的排在后面，符合要求。

根据以上举例可以看出来，在对多个字段排序的时候，往往需要稳定的排序算法进行排序。

这也是为什么同样的时间复杂度，在有些时候能用不稳定的快排，有些时候用稳定归并排序。

?

?