万字总结，数据结构_内部排序_大总结，一篇就够了_数据结构内部排序总结

总分类：

内部排序

数据量较小，全部数据能够在内存中完成排序，本文中所有排序均为从小到大排序

1. 插入排序

插入排序是一种最为简单的排序方法之一，为了保证随机访问的效率，插入排序应使用数组结构完成对元素的随机访问。其总体思想分为三步

插入排序的执行图解如下

插入排序根据定位插入位置的方式不同可以有直接插入排序、折半插入和希尔排序等，这里介绍三种最为常用的插入排序方式：

1.1 直接插入排序

1.1.1 直接插入排序原理

最简单的插入排序的方式就是直接插入排序:
直接插入排序是指——
对于N个元素,从0开始的数组：某序列的N个元素Element[0]~Element[N-1]，可以遍历1到N-1的元素(从数组的第二个元素开始遍历)，也就是进行N-1趟操作。

排序过程中，使用“ i ”作为当前遍历元素的位置标记，在某一趟排序，序列Element[ ]的前i-1个元素Element[0]～Element[ i-1 ]已经有序，而范围Element[ i ] ~ Element[ N-1 ] 未有序，本躺排序中从范围Element[ 0 ]～Element[ i-1 ]中寻找某个位置（用“ j ”来标记当前需要插入的位置），将Element[ j ] ~ Element[ i-1 ]后移一位至Element[ j+1 ] ~ Element[ i ]，后移元素后将Element[ i ]插入该位置，此时范围Element[ 0 ] ~ Element[ i ]有序。

具体执行图示如下：
原序列如下：

第一次排序：
左侧部分为有序部分，右侧为待排序部分,从第二个元素进行排序，4 > 3（Element[ 1 ] > = Element[ 0 ]），原序列有序，不挪动位置

第二次排序：
左侧部分为有序部分，右侧为待排序部分,对 Element[ 2 ] 进行排序，2 > 3（ Element[ 2 ] < Element[ 0 ] ),插入位置是Element[ 0 ]，Element[ 0 ]~Element[ 1 ]，后移一位然后插入

第三次排序：
左侧部分为有序部分，右侧为待排序部分,对 Element[ 3 ] 进行排序，5 > 4（ Element[ 2 ] < Element[ 3 ] ),原序列有序，不挪动位置

第四次排序：
左侧部分为有序部分，右侧为待排序部分,对 Element[ 4 ] 进行排序，4 > 3（ Element[ 4 ] < Element[ 2 ] ),插入位置是Element[ 2 ],将 Element[ 2 ]~Element[ 3 ]后移一位然后插入

四次排序完成后结果如下：

1.1.2 直接插入排序动态图解

排序图解使用上述实例：

1.1.3 直接插入排序代码

本例中给出直接插入排序的C代码，这里介绍两种书写方式，第一种就是较为传统的插入排序方式，若temp小于j指向的元素便进行后移。
第一种书写方式具体如下

//第一种书写方式
void Insert_sort_inline(int Element[],int N) {
	int temp = 0;
	int j = 0;
	int i = 1;
	for (i = 1; i < N; i++){//第一个For循环完成N-1个元素的遍历
		temp = Element[i];
		j = i;
		while(j>0&&temp<Element[j-1]) {//为方便后移元素位置，从后向前扫描，若temp小于j指向的元素便进行后移
			Element[j] = Element[j - 1];
			j--;
		}
		Element[j] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第二种直接插入排序程序的书写方式是对数组进行特殊定义，例如一个数组，一般的定义如下：

int A[]={1,2,3,4,5}
1

其中A[0]=1,A[1]=2……以此类推，在使用数组时可以使用一个数组中的元素作为简化边界条件的变量，从而防止遍历数组时发生越界。这个数组的变量一般使用数组中的边界元素作为中间变量，也可以称之为哨兵。
例如，可以使用A[0]元素作为该数组的哨兵，也就是使用A[0]作为查找插入位置的边界条件
所以第二种书写方式具体如下

void Insert_sort_inline_with_sentry(int Element[], int N) {
	int i=0, j=0;
	for (i = 2; i <=N; i++) {
		Element[0] = Element[i];
		//这里可以使用For循环完成排序
		//for (j = i - 1; Element[0] < Element[j]; j--)
			//Element[j + 1] = Element[j];
		j = i;
		while(Element[0]<Element[j-1]) {
			Element[j] = Element[j - 1];
			j--;
		}
		Element[j]=Element[0];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

插入排序需要使用到数组的随机访问特性，但并不意味着链式结构不可以使用插入排序，链式结构有多个自由指针能够定位元素绝对位置和相对位置也可以是一个插入排序。
编程是灵活的，但效率是唯一的。

1.1.4 直接插入排序的复杂度与稳定性

稳定性主要考虑对于相同元素排序完成后是否保持原顺序，本例中的$3$与$\underline{3}$在排序完成后仍旧保持原序。所以直接插入排序为稳定的排序。

1. 最好情况：原序列有序，此时复杂度为$O(N)$
2. 最坏情况：原序列为逆序，时间复杂度为$O(N^2)$
3. 平均时间复杂度：$O(N^2)$
4. 空间复杂度为常量：$O(1)$

1.2 折半插入排序

在寻找插入位置过程中使用折半查找的方式查找插入位置，这种插入方式称作折半插入排序。
插入排序的“ i ”前的所有元素都是有序的，所以可以很方便的使用折半查找完成插入位置的查找。这里简单介绍折半查找：

1.2.1折半查找

折半查找其实就是使用二叉树排序树完成查找操作,这里给出一个二叉排序树的结构供读者参考。二叉排序树的特点如下：
1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于它的的根结点的值；
3. 左、右子树也分别为二叉排序树；
4. 没有值相等的结点。

对于有序队列可以生成如下的排序树，对于排序树的查找不是本文讨论的重点，后续笔者会更新查找算法的总结。二叉排序树查找的节点Element[mid]就是排序树的根节点，若查找的值大于根节点就转向右子树，小于根节点的值就转向左子树。

1.2.2 折半查找图解

以序列Element[ ]={1,2,3,4,5,6,7,8}为例查找7的执行图解如下：

1.2.3 折半查找代码

折半查找代码如下：

//x表示需要查找的元素
int Half_fold_search(int Element[], int low, int heigh,int x) {
	
	while (low<=heigh)
	{
		int mid = (low + heigh) / 2;//定义中间变量
		if (Element[mid] == x)//如果找到元素位置，返回位置
			return mid;
		else if (x > Element[mid])
			low = mid + 1;
		else
			heigh = mid - 1;
		
	}
	return -1;//low>heigh，返回-1表明序列中没有需要查找的元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.2.4 折半插入排序图解

本例中给出折半查找位置后的$low$和$heigh$两个标记找到插入位置时的位置，如下，插入位置可以为$low$和$heigh+1$：

1.2.5 折半插入排序代码

本文中给出使用哨兵的折半插入排序的代码，读者可以根据实际的应用进行简单的修改：

//折半插入排序
void Half_fold_Insert_sort(int Element[],int N) {
	int i = 0, j = 0, mid = 0, low = 0, heigh = 0;
	for (i = 2; i <N;i++) {
		//折半查找插入位置
		Element[0] = Element[i];
		low = 1;
		heigh = i - 1;
		while (low<=heigh)
		{
			mid = (low + heigh) / 2;
			if (Element[mid] > Element[0])
				heigh = mid - 1;
			else
				low = mid + 1;
		}
		//找到插入位置后后移元素
		for (j = i - 1; j >= heigh+1; j--)
			Element[j + 1] = Element[j];
		//在找到的位置插入元素
		Element[heigh + 1] = Element[0];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.2.6 折半插入的排序复杂度与稳定性

折半插入排序为稳定的排序方法。

折半查找仅仅优化了比较次数比较次数的数量级为$O(N{\log }_{2}N)$，由于N会影响二叉排序树的树高，所以折半查找的比较次数与初始排序是否有序无关，只与序列元素个数有关。但是优化比较次数仍旧需要后移元素，所以时间复杂度为$O(N^2)$

1. 平均时间复杂度：$O(N^2)$
2. 空间复杂度为常量：$O(1)$

1.3 希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序其实也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破$N^2$的第一批算法之一。
希尔排序的思想其实是一种分组插入的方法

希尔排序的目标是使数组中间任意间隔h的元素有序。其中每隔h的元素组成h有序数组。一个h有序数组就是由h个有序子数列组成的数组
例如：
一个长度为16的数组，h=4时如下图：
上图中每隔4个元素分组，每个分组由4个元素构成，一个4-有序数组

一个长度为16的数组，h=5时如下图：

上图中每隔5个元素分组，一个5-有序数组

1.3.1 希尔排序图解

为了方便读者理解，以下给出希尔排序的图解，如下（可以单击放大查看）：

代码如下，

void Shell_Sort(int Element[],int N) {
	int step = 0,i = 0,temp=0,j=0;
	for (step = N / 2; step >= 1;step/=2) {//调整步长，步长缩短倍数为2
		for (i = step; i < N; i++) {
			if (Element[i] < Element[i - step]) {//比较每一组元素
				temp = Element[i];
				for (j = i - step; j >= 0 && temp < Element[j]; j -= step)//后移元素
					Element[j + step] = Element[j];
				Element[j + step] = temp;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3.2 希尔排序的复杂性与稳定性

稳定性：
希尔排序会将序列按照定长的步长进行分组，所以对于值相同的元素无法保证保证原序列的相对位置，希尔排序是一种不稳定的排序算法。
时间复杂度：
希尔排序的复杂度和递增序列是相关的，算法的性能不仅仅取决于h，还取决于h之间的数学性质，比如分组为（4，2，1）或者分组为（9，3，1）。所以很难去描述其对乱序的数组性能特征的排序方法。针对不同的递增序列序列会有不同的时间复杂度。

• {1,2,4,8,…}这种序列并不是很好的递增序列，使用这个增量序列的时间复杂度（最坏情形）是$N^2$
• Hibbard提出了另一个递增序列{1,3,7，…,$2^k-1$}，这种序列的时间复杂度(最坏情形)为$N^{3/2}$
• Sedgewick提出了几种递增序列，其最坏情形运行时间为$N^{1.3}$,其中最好的一个序列是{1,5,19,41,109,…}

希尔排序对中等大小的数组还是具有很好的性能的，代码量小，并且不需要额外空间。对于不要求极端的运行环境情况下是一个不错的选择。

2. 交换排序

交换排序的思想是每次选两个元素进行比较并交换位置，最为常见的交换排序就是冒泡排序与快速排序。

2.1 冒泡排序

冒泡排序是一种极为形象的交换排序方式，序列以冒泡的方式进行排序，从下至上每两个元素进行交换排序。

2.1.1冒泡排序图解

这种交换排序方式相信读者能够根据图示加以理解，图解如下：

2.1.2 冒泡排序代码

/// 冒泡排序
void Bubbling_Sort(int Element[],int N) {
	int temp = 0;
	for (int i = 0; i < N - 1; i++) {
		bool flag = false;//设置交换标志位，如果为真表示发生过交换
		for (int j = N - 1; j > i;j--) {
			//从后向前排序先找最小的元素
			if (Element[j-1]>Element[j]) {//当前元素大于前一元素，发生交换
				temp = Element[j - 1];
				Element[j - 1] = Element[j];
				Element[j] = temp;
				flag = true;//修改标志位，表明发生过交换
			}
			
		}
		if (flag == false)//序列已经有序，不需要进行排序
			return;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.1.3 冒泡排序的复杂性与稳定性

1. 平均时间复杂度：$O(N^2)$
2. 空间复杂度为常量：$O(1)$

冒泡排序对链表有良好的适应能力，并不依赖数组的随机访问性，是一种稳定的排序方式。

2.2 快速排序

读者理解快速排序时可以先尝试阅读本文的归并排序，这样有助于理解分治的思想

快速排序过程其实也是一种分治的排序算法，快速排序与归并排序事互补的，归并排序将数组分成两个子数组分别排序，通过递归的方式将有序的子数组归并从而得到整个有序的数组。
所以排序算法的步骤主要是：

1. 先从数列中取出一个数作为基准数。
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3. 再对左右区间重复第二步，直到各区间只有一个数。

快速排序总体上使用的仍旧是交换的思想，如下图，设置两个“指针”从两侧开始遍历序列，找到左半部分大于6，右半部分小于6的元素进行交换。

2.2.1 快速排序图解

2.2.2 快速排序代码

/// <快速排序>
/// </分组排序过程>
int Partition(int Element[],int low,int heigh) {
	int Current_Element = Element[low];//选择标志元素
	while (low<heigh)
	{
		while (low < heigh && Element[heigh] >= Current_Element)
			--heigh;//元素小于标志元素的移动到左端
			Element[low] = Element[heigh];
		while (low < heigh && Element[low] <= Current_Element)
			++low;//元素大于标志元素的移动到右端
			Element[heigh] = Element[low];
	}
	Element[low] = Current_Element;
	return low;
}
/// <快速排序>
/// </排序过程>
void Quick_Sort(int Element[], int low, int heigh) {
	if (low < heigh) {
		int Current_Element = Partition(Element, low, heigh);
		//对左右两部分
		Quick_Sort(Element,low, Current_Element-1);
		Quick_Sort(Element, Current_Element+1,heigh);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.2.3 快速排序的复杂性与稳定性

快速排序是一种不稳定的排序方法。与折半查找插入排序类似，快速排序其实是对于红黑树的应用。
其平均时间复杂度为：$O(N{\log }_{2}N)$
平均空间复杂度为：$O({\log }_{2}N)$
快速排序对于部分有序的序列应用性不强，若序列有序其时间复杂度约为$O(N^2)$

3 选择排序

选择排序的思想是：每次从待排序列中选择最小元素存放在有序列中，直到待排序列中的元素仅剩一个为止。

3.1 简单选择排序

简单选择排序执行过程较为简单，本文中直接给出代码，不再作详解。

3.1.1 简单选择排序代码

void Simple_Select_Sort(int Element[], int N) {
	//简单选择排序
	int min = 0;
	int temp = 0;
	for (int i = 0; i < N; i++) {//遍历序列中的所有元素
		min = i;
		for (int j = i + 1; j < N; j++)//在当前元素到最后元素之间找到最小值
			if (Element[j] < Element[min])
				min = j;
		if (min != i) {//交换
			temp = Element[i];
			Element[i] = Element[min];
			Element[min] = temp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.1.2 简单选择排序的复杂性与稳定性

简单选择排序是一种不稳定的排序方法。这是由于在排序过程中每次只选择单个元素完成排序过程。
空间复杂度：$O(1)$
时间复杂度：$O(N^2)$

3.2 堆排序

选择排序的优化是对选择方式和选择过程的优化，堆排序就是一种简化选择的优秀方式。

3.2.1 堆排序的执行图解

堆排序由建堆和排序两部分构成，示例序列如下：

第一次建堆过程如下：
根据数组表示各元素之间的的位置建立二叉树

从$E[\lfloor N/2\rfloor ]$处开始完成调整，首先检查$E[\lfloor N/2\rfloor ]$处是否有左右节点，若有，找出左右节点的最大值与本节点比较，找到最大值与当前值进行替换，本例中从$E[4]$处开始调整：
在$E[4]$处调整完成后遍历$E[3]$节点，比较两个子节点中的最大值为64小于77，因此不做调整

在$E[3]$处调整完成后遍历$E[2]$节点，比较两个子节点中的最大值为31小于44，因此不做调整，$E[1]$处同样操作，所以大根堆如下：

整体的排序方法如下：

3.2.2 堆排序的执行代码

//进行根堆调整建立
void Root_Pile(int Element[], int k, int N) {
	 Element[0] = Element[k];
	 for (int i = 2 * k; i < N; i *= 2) {
		 if (i < N && Element[i] < Element[i + 1])
			 i++;
		 if (Element[0] >= Element[i])
			 break;
		 else {
			 Element[k] = Element[i];
			 k = i;
		 }
	}
	 Element[k]=Element[0];
}
///建立大根堆
void Buid_Large_Root_Pile(int ELement[],int N) {
	for (int i = N / 2; i >= 0; i--)
		Root_Pile(ELement,i,N);
}
//堆排序过程
void Heap_Sort(int ELement[], int N) {
	int temp = 0;
	Buid_Large_Root_Pile(ELement,N);
	for (int i = N; i > 1; i--) {
		temp = ELement[i];
		ELement[i] = ELement[1];
		ELement[1] = temp;
		Root_Pile(ELement,1,i-1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3.2.3 堆排序的复杂性与稳定性

堆排序是一种不稳定的排序方法。
空间复杂度为：$O(1)$
时间复杂度为：$O(N{\log }_{2}N)$

4 归并排序

归并采用的是一种分治的思想，将一个序列看作很多很小的序列组合，归并的过程就是将当前有序序列进行合并。
比如，就二路归并而言，就是将两个有序表合并成一个有序表，从而得到一个完整的有序序列。
归并是一种牺牲空间从而窃取时间效率的思想

归并排序的特点如下，读者可以根据图解以及代码理解以下两点内容：

• 归并排序能够保证将任意长度为$N$的数组排序所需时间和$N{\log }_{2}N$成正比；
• 归并排序的主要缺点是其所需的额外空间与$N$成正比。
  注:本文介绍的归并以二路归并为主，多路归并在外部排序中应用较广，本文不涉及外部排序。

4.1 原地归并排序方法

这里介绍一种归并排序最为常用的方式——实现归并的一种方式就是直接将两个有序数组归并到另一个数组中。图示如下：

1. 首先将左右序列排序好的数组$a[k]$所有元素复制到$aux[k]$中：

2. 然后将$aux[k]$中的元素归并到$a[k]$中。

• 如果右方元素较小将$aux[j]$中的元素归并到$a[k]$中,
• 如果左方元素较小将$aux[i]$中的元素归并到$a[k]$中。
  
  
  左边用尽直接将后半部分$aux[j]$复制到$a[k]$

原地归并算法如下：

void Merge(int Element[],int Element_Copy[], int low, int mid, int heigh) {//完成两个序列的归并过程
	//完成两个序列的复制
	for (int h = low; h <= heigh; h++)
		Element_Copy[h] = Element[h];
	int i = low, j = mid + 1,k=low;
	for (int k = low; i < mid + 1 && j <= heigh; k++) {
	//比较序列两部分的大小，小元素复制回原序列中
		if (Element_Copy[i] <= Element_Copy[j])
			Element[k] = Element_Copy[i++];
		else
			Element[k] = Element_Copy[j++];
	}
	while (i <= mid)
		Element[k++] = Element_Copy[i++];
	while (j <= heigh)
		Element[k++] = Element_Copy[j++];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

递归的调用原地排序过程就可以完成递归排序。

4.2 自顶向下的归并排序

4.2.1 自顶向下的归并排序图解

自顶向下其实是先完成左侧数组然后完成右侧数组的排序规则：

4.2.2 自顶向下的归并排序代码

void Merge_Sort_Top_Down(int Element[], int Element_Copy[], int low, int heigh) {
	//自顶向下的归并排序
	if (low < heigh) {
		int mid = (low + heigh) / 2;
		Merge_Sort_Top_Down(Element,Element_Copy,low,mid );//先对左侧序列进行归并排序
		Merge_Sort_Top_Down(Element, Element_Copy, mid + 1, heigh);//对右侧元素进行归并排序
		Merge(Element,Element_Copy,low,mid,heigh);//归并操作
	}
}
1
2
3
4
5
6
7
8
9

其实Merge_Sort的的作用只是对merge执行的顺序完成合理调用。

这里直接给出对于长度为$N$的数组，自顶向下的归并排序的比较次数：$1/2NlgN$~$NlgN$
访问数组的次数(最多)：$6NlgN$

4.3 自底向上的归并排序

4.3.1 自底向上归并排序图解

自底向上其实就是从所有数组中最小分组进行归并排序
首先进行分解，也就是递归过程先分解后排序：

当分解到最简元素时进行原地归并：

4.3.2 自底向上归并排序代码

读者可以根据自底向上的归并排序的代码进一步理解归并操作，自底向上的归并排序的核心就是序列的分组：

void Merge_Sort_Down_Top(int Element[], int Element_Copy[], int N) {
	int heigh_min=0;
	for (int sz = 1; sz < N; sz = sz + sz) {//设置归并的子串长度
		for (int lo = 0; lo < N - sz; lo += sz + sz)//设置子串的起始位置
		{	//if语句相当于min(N-1,lo+sz+sz-1)，子串最长不能超过N-1
			if ((N - 1) > (lo + sz + sz - 1))
				heigh_min = lo + sz + sz - 1;
			else
				heigh_min = N - 1;
			Merge(Element, Element_Copy, lo, lo + sz - 1, heigh_min);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里直接给出对于长度为$N$的数组，自顶向下的归并排序的比较次数：$1/2NlgN$~$NlgN$
访问数组的次数(最多)：$6NlgN$

4.4 归并排序复杂性与稳定性

归并操作不会改变相同关键字的相对顺序，所以归并排序是一种稳定的排序方法。
空间复制度：$O(N)$
时间复杂度：$O(N{\log }_{2}N)$
时间复杂度主要是由两部分构成，归并操作的时间复杂度为$O(N)$，进行二路归并的操作受归并树的树高影响数量级为$O({\log }_{2}N)$

5 基数排序

5.1 基数排序图解

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。原理是将序列按位数（或其他方式）切割成不同的位，然后按每位分别比较。基数排序总体上可以分为两类：

1. MSD：先从高位开始进行排序，
2. LSD：先从低位开始进行排序，
   执行示例如下：
   

5.2 基数排序代码

int Max_Bit(int Element[], int N) //求数据的最大位数
{
	int maxData = Element[0];      
	/// 先求出最大数，再求其位数
	for (int i = 1; i < N; ++i)
	{
		if (maxData < Element[i])
			maxData = Element[i];
	}
	int d = 1;
	int p = 10;
	while (maxData >= p)
	{
		//p *= 10; // Maybe overflow
		maxData /= 10;
		++d;
	}
	return d;

//基数排序
void Radix_Sort(int Element[], int N)
{
	int d = Max_Bit(Element, N);
	int* tmp = new int[N];
	int* count = new int[10]; //计数
	int i, j, k;
	int radix = 1;
	for (i = 1; i <= d; i++) //进行d次排序
	{
		for (j = 0; j < 10; j++)
			count[j] = 0; //每次分配前清空计数器
		for (j = 0; j < N; j++)
		{
			k = (Element[j] / radix) % 10; //统计每个记录中的数量
			count[k]++;
		}
		for (j = 1; j < 10; j++)
			count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个序列
		for (j = N - 1; j >= 0; j--) //将所有记录依次收集到tmp中
		{
			k = (Element[j] / radix) % 10;
			tmp[count[k] - 1] = Element[j];
			count[k]--;
		}
		for (j = 0; j < N; j++) //将临时数组的内容复制到序列中
			Element[j] = tmp[j];
		radix = radix * 10;
	}
	delete[]tmp;
	delete[]count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

5.3 归并排序复杂性与稳定性

基数排序是一种针对特定数据格式的排序方式，不需要进行元素之间的比较即可完成序列的排序，是一种比较特殊的比较算法。是一种稳定的排序算法。

• 空间复杂度：$O(R)$
• 基数排序需要进行D趟分配和收集，一趟分配需要O(N);一趟收集需要O®，所以基数排序的时间复杂度为$O(D(N+R))$

6 各种排序算法总结

空间与时间复杂度总结如下（点击放大观看即可）：

对于排序算法而言，快速排序是理论上效果最佳，快速排序是一种利用红黑树思想进行排序的方法，代码简单是一种常用且极为高效的排序算法。
对于堆排序，尽管空间复杂度较低，但是每次排序都会进行根堆的调整，算法执行过程中做了许多无用功。