【数据结构】各种排序方法的时间复杂度，空间复杂度就，稳定性的总结分析_各排序算法的时间复杂度和空间复杂度

各个算法的时间复杂度与空间复杂度、稳定性

排序方法 最好 最坏 时间复杂度 平均 空间复 杂度 稳定性 
直接插入 O(n) O(n²) O(n²) O(1) 稳定 
希尔排序 O(n) O(n²) O(n1.3) O(1) 不稳定 

目录

各个算法的时间复杂度与空间复杂度、稳定性

各个排序算法的分析

直接插入排序

希尔排序

冒泡排序

快速排序

直接选择排序

堆排序

归并排序

期末试题

---

冒泡排序 O(n) O(n²) O(n²) O(1) 稳定 
快速排序 O(nlog2n) O(n²) O(nlogzn) O(logzn) 不稳定 
简单选择 O(n) O(n²) O(n²) O(1) 不稳定 
堆排序 O(nlogzn) O(nlogzn) O(nlogzn) O(1) 不稳定 
归并排序 O(nlogzn) O(nlogzn) O(nlogzn) O(n) 稳定 
基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(n+rd) 稳定

排序的稳定与否本质上是看其能否让相同的两个数在排序过程中，相对位置保持不变

详细可参考这篇文章：

排序方法稳定性总结_有哪些排序是稳定的_醉卧考场君莫笑的博客-CSDN博客

各个排序算法的分析

直接插入排序

直接插人排序是插入类排序算法中较简单、直接的排序方法，基本思想是:将整个待排表看作左右两部分,其中左边为有序区,右边为无序区,整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。

【算法分析】
①的元素时停止了,所以该算法为稳定的排序算法。
②空间性能:该算法仅需要一个记录的辅助存储空间，即监视哨的空间。
0时间性能:整个算法循环n-1次,每次循环中的基本操作为比较和移动元素，其总次数取决于数据表的初始特性，可能有以下几种典型的情况:
数据表开始时已经有序,因而每次循环中只需比较一次，移动两次,所以整个排序算去的比较和移动元素次数分别为(n-1)和2(n-1),因而其时间复杂度为O(n)。
·当数据表为逆序时，每次循环中比较和移动元素的次数达到最大值，分别为i和i+1
次，因而整个算法的比较和移动元素次数达到最大值，分别为∑i=(n+2)(n-1)/2和
之i+1=(n+4)(n-1)/2。因而算法的时间复杂度为O(n)。
。一般情况下，可认为出现各种排列的概率相同，取上述两者的平均值作为其时间性能,因而时间复杂度为 O(n)。

希尔排序

希尔排序的基本思想是：将待排序列划分成若干组，每组内进行直接插入排序，以使整个序列基本有序，然后再对整个序列进行直接插入排序。

详细知识点可参考：【排序算法】希尔排序（C语言）_希尔排序c语言_手眼通天王水水的博客-CSDN博客

【算法分析】

希尔排序时间性能是一个复杂的问题，考虑到每一趟都是上一躺的基础上进行的，故可以认为是基本有序，因而各趟的时间复杂度为O（n）;由于按每次步长的一半进行，故需要的躺数为log2n;由此可知，整个排序算法的时间复杂度为O（nlog2n）。另外，该算法显然是不稳定的。

冒泡排序

冒泡排序的基本思想是:从一端开始，逐个比较相邻的两个元素，发现倒序即交换。典型的做法是从后往前，或从下往上逐个比较相邻元素,发现倒序即进行交换，本书默认为按这一方向进行。这样一遍下来，一定能将其中最大(或最小)的元素交换到其最终位置上(按此处的约定,为最上面),就像水中的气泡那样冒到水面上，故此得名。然而，一趟只能使一个“气泡”到位，所以必须对余下元素重复上述过程,即要重复n-1次冒泡操作。

【算法分析】

本算法的时间复杂度依赖于待排序序列的初始特性,典型地有如下几种情况: 
做法
方向 ①当初始序列为正序时,仅一趟比较下来即可结束,因而所进行的比较元素的次数为n 
的约 -1次，而交换次数为0,所以时间复杂度为O(n)。 
2、当初始序列为逆序时,每一趟中的比较和交换元素的次数均达最大值,其中第i趟中 
非序 的比较和交换次数均为(n-i),因而整个算法的比较和交换次数为n(n-1)/2,故算法的时 
间复杂度为O(n²)。
③假设一般情况下出现各种排列的概率相同，则将上述两种情况的时间复杂度的平均值作为其时间复杂度，因此为O(n²)。
该算法显然是稳定的排序算法。

快速排序

快速排序的基本思想是:首先,选定一个元素作为中间元素,然后将表中所有元素与该中间元素相比较，将表中比中间元素小的元素调到表的前面，将比中间元素大的元素调到后面,再将中间数放在这两部分之间以作为分界点,这样便得到一个划分。然后再对左右两部分分别进行快速排序(即对所得到的两个子表再采用相同的方式来划分和排序，直到每个子表仅有一个元素或为空表为止。此时便得到一个有序表)。
也就是说，快速排序算法通过一趟排序操作将待排序序列划分成左右两部分，使得左边任一元素不大于右边任一元素，然后再分别对左右两部分分别进行(同样的)排序,直至整个序列有序为止。
由此可见，对数据序列进行划分是快速排序算法的关键。

详细知识点可参考：快速排序法（详解）_李小白~的博客-CSDN博客

这种排序方法显然是不稳定的。

理想情况下，每次选取的中间元素恰好能将子表划分成两个部分，此时时间复杂度为O（nlog2n）

另一个极端情况是，每次所选的中间元素为其中最大或者最小的元素，这将使得每次划分将其中一个表划分为空表，另一个子表长度为原表长度-1；

一般情况下，所选择的中间元素是最大或者最小的概率较小，因此可以认为快速排序算法的平均时间复杂度为O(knlog2n）,其中k为某常数。

从平均时间性能来说，快速排序被认为是目前最好的内部排序方法。

int lu_part(element r[], int l, int h) {
	int i = l;
	int j = h;
	int ele = r[i];//中间元素
	while (i < j)
	{
		while (i<j && r[j]>ele) //从右向左开始找一个 小于等于 pivot的数值
		{
			j--;
		}
		if (i < j)
		{
			swap(r[i], r[j]);
			i++;//r[i]和r[j]交换后 i 向右移动一位
		}
		while (i < j && r[i] <= ele) //从左向右开始找一个 大于 pivot的数值
		{
			i++;
		}
		if (i < j)
		{
			swap(r[i], r[j]);
			j--;//r[i]和r[j]交换后 i 向左移动一位
		}
	}
	return i;  //返回最终划分完成后中间元素所在的位置，便于下次分割
}
void Quicksort(element r[], int low, int hight)
{
	int mid;
	if (low < hight)
	{
		mid = lu_part(r, low, hight);  // 返回基准元素位置
		Quicksort(r, low, mid - 1); // 左区间递归快速排序
		Quicksort(r, mid + 1, hight); // 右区间递归快速排序
	}
}
/*void partition(element a[], int s, int t, int* cutPoint) {
	//对数组A中下标为s~t的子表进行划分，并且用cutPoint返回中间元素的位置
	element x = a[s];
	//保存中间元素
	element i = s;
	element j = t;
	while (i != j) {
		while (i<j && a[j]>x) {
			j--;
		}
		if (i < j) {
			a[i] = a[j];//成功找到
			i = i + 1;
		}
		while (i < j && a[i] < x) {
			i++;
		}
		if (i<j) {
			a[j] = a[i];
			j = j - 1;
		}
		
	}
	a[i] = x;
	*cutPoint = i;
}*/

直接选择排序

直接选择排序算法采用的方法较为直观：通过待排子表中完整地比较一遍以确定最大（小）元素，并将该元素放在子表的最前（后）面。

【算法分析】

稳定性：该算法是不稳定排序，因为相同关键字的元素在排序过程中可能交换次序。

时间复杂度：该算法共进行了n(n-1)/2次比较，交换次数最多为n-1次。因而时间复杂度为O（n^2）

空间复杂度：O（log2n）

堆排序

详情知识点可参考：堆排序详细图解（通俗易懂）_右大臣的博客-CSDN博客

【算法分析】

空间复杂度：O（1）

堆排序算法花费时间最多的是建初始堆和调整堆时所进行的筛选。对深度为k的堆，筛选算法中所进行的关键字的比较次数至多为2(k-1)次,而n个结点的完全二叉树的高度为log2n+1,因此调整堆(共n-1次)总共进行的关键字的比较次数不超过 logz(n-1)+log2(n-2)+…+(logz2),而建初始堆所进行的比较次数不超过4n，因此算法的时间复杂度为 O(nlog2n)。

归并排序

归并排序是一种基于归并方法的排序，所谓“归并”是指将两个及两个以上的有序表合并成一个新的有序表。

详细知识点可参考：归并排序（分治法）_分治法实现归并排序_小小的香辛料的博客-CSDN博客

【算法分析】

空间性能：由于顺序表不能进行就地归并，因而需另外开辟储存区以存放归并结果，所以归并排序需要与原表等量的辅助存储空间。空间复杂度为O（n）

时间性能：由于将两个有序表合并成一个有序表的时间复杂度为原两表长的数量级，一次排序一趟的时间复杂度为O（n）,总共需要log2n次归并，故时间复杂度为O（nlog2n）

归并排序属于稳定排序

期末试题

1.对下面数据表执行快速排序，写出每一趟排序的结果，并标出第一趟排序过程中的元素移动情况。
(50,20,80,30,65,18,75,10,150,22,75,110,200,25)

1、【解析】

快速排序需要首先需要选择一个中间元素，然后用表中各个元素与其进行比较。本题可采用第一个元素作为中间元素，例如第一趟选择50，第二趟选择25和75.

第一趟排序结果:25,20,22,30,10,18,50,75,150,65,75,110,200,80;第二趟排序结果:18,20,22,10,25,30,50,75,65,75,150,110,200,80;第三趟排序结果:10,18,22,20,25,30,50,65,75,75,80,110,150,200;第四趟排序结果:1018,20,22,25,30,50,65,75,75,80,11,15,200
【考点延伸】快速排序

2.给定数据序列 11、21、7、16、6、3、18514820。按从小到大排序时，给出下列算算法前2趟排序的序列。①(6 分)堆排序。
②(6分)快速排序(2 趟划分后的的结果)。

3.对下面的数据表，写出采用快速排序算法排序的每一趟的结果。

66 17 34 75 58 100 25 10 81 3 45

4.快速排序的空间复杂度为：_______

[答案]O（log2 n）（最好情况）/O(n)(最坏情况)

注：文章主要参考：《数据结构》安徽大学出版社，主编胡成钢，张先宜