数据结构与算法——排序算法

目录

文章目录

前言

一.排序的基本概念

1.什么是就地排序

2.什么是内部排序和外部排序

3.什么是稳定排序

4.判定一个排序算法的是稳定的

二.插入排序算法

1.直接插入排序

1.1基本思想

1.2复杂度

1.3稳定性

1.4代码演示

2.折半插入排序

2.1基本思想

2.2性能

3.2-路插入排序算法

4.希尔排序

4.1基本思想

4.2 性能

4.3Hibbard增量序列

4.4更多的增量序列

4.5代码演示

三.交换排序

1.冒泡排序

1.1算法思想

1.2关于冒泡的优化

1.3复杂度分析

1.4如何用两个栈实现冒泡

1.5详细解析

1.6代码演示

2.快速排序

2.1算法思想

2.2复杂度分析

2.3快速排序的稳定性从哪里来

2.4代码演示

四.归并和计数排序

1.归并排序

1.1算法思想

1.2复杂度分析

1.3代码演示

2.计数排序

2.1算法思想

2.2稳定性

2.3复杂度分析

3.桶排序

3.1桶排序的思想

3.2关于桶排序的算法分析

3.3桶排序适用情况

4.基数排序

4.1算法思想

4.2复杂度分析

五.选择排序（二叉堆）

1.堆

2.二叉堆

3. 二叉堆的存储结构

4. 小顶二叉堆常见的操作

5.简单的选择排序与堆排序代码演示

---

---

前言

排序算法的重要性不言而喻在算法竞赛中经常考到因此我们要好好学习！

---

一.排序的基本概念

1.什么是就地排序

使用恒定的额外空间，只需要使用他给你的数据
一个就地排序算法使用恒定的的额外空间来产生输出（仅修改给定的数组）。它仅通过修改线性表中元素的顺序来对线性表进行排序。
例如，插入排序和选择排序是就地排序算法，因为它们不使用任何额外的空间来对线性表进行排序。而归并排序和计数排序的经典实现就不是就地排序算法

2.什么是内部排序和外部排序

待排序数据，是否可以一次性的载入到内存中
当所有待排序记录不能被一次载入内存进行处理时，这样的排序就被称为外部排序。
外部排序通常应用在待排序记录的数量非常大的时候。归并排序以及它的变体都是典型的外部排序算法。外部排序通常与硬盘、CD等外部存储器（辅存）关联在一起。当所有待排序记录可以一次载入内存时，则称为内部排序。

3.什么是稳定排序

判断相同的关键字，排序以后，相对位置的变化，处理键值对的时候
当我们对可能存在重复键的键值对（例如，人名作为键，其详细信息作为值）按照键对这些对象 进行排序时，稳定性就显得至关重要

4.判定一个排序算法的是稳定的

如果两个具有相等关键字的对象在排序前后的相对位置没有发生变化，则认为排序算法是稳定的。可以形式化地描述为：
设A表示一个待排序的数组， <表示数组A的一个严格的弱排序（即有重复元素）。一个排序算法稳定，当且仅当i < j^A[i]≡A[j] ，且隐含π(i) < π(j)，其中π表示排序后的序列（排序算法将A[i]移动到了π(i)的位置，将A[j]移动到了π[j]的位置，但是i和j的相对位置保持不变)。

图中展示的就是稳定排序的例子，简单来讲，排序前，青色球 10 在蓝色球 10 的前面，那么排序后两者的相对位置并没有改变，青色球 10 还是在红色球的前面；排序前蓝色球 20 在青色球 20 的前面，则排序后两者的两者的位置没有发生变化，依旧是蓝色在青色的前面

简而言之，排序前后序列中键值相等的元素的相对位置没有发生变化的就是稳定排序

二.插入排序算法

1.直接插入排序

在玩扑克牌的时候，我们抽到一张牌的时候，都是将它插入到当前手中牌的合适位置的。直接插入排序也是这样的思想

1.1基本思想

插入排序的思想是：
将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。初始时，有序序列的长度为1。

给定序列 [9 , 20 , 13 , 10 , 12 ] 。初始状态如下：

 分成的两个序列如下：

也就是说，此时我们讲数组当中的第一个元素9当作有序元素。
第一次插入：将20和9做比较，20>9，顺序没有问题。不动。

第二次插入：将13与20比较，13<20，此时20就要先到13的位置。再跟9比较，13>9，那么此时
将13插入到9后面

第三次插入，将10和20比较，10<20，20去10的位置，再将10和13比较，10<13，则13也往下移动，再将10和9比较，10>9，则将10插入到9的后面

第四次插入：将12和20比较，12 <20，20后移，再将12和13比较，12<13，13后移，再将12和10比较，12 > 10,将12插入到10的后面

1.2复杂度

在排序前元素已经是按需求有序了，每趟只需与前面的有序元素序列的最后一个元素进行比较，总的排序码比较次数为n-1，元素移动次数为0。时间复杂度为 O(n);
而在最差的情况下，及第i趟时第i个元素必须与前面i个元素都做排序码的比较，并且每做一次就叫就要做一次数据移动，此时的时间复杂度为O(n^2) ；所以直接插入排序的时间复杂度为O(n^2) 插入排序不适合对大量数据进行排序应用，但排序数量级小于千时插入排序的效率还不错，可以考虑使用。插入排序在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。直接插入排序采用就地排序，空间复杂度为O（1）

1.3稳定性

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。如果碰见一个和插入元素相等的，那么将会把待插入元素放在相等元素的后面。所以，相等元素的相对的前后顺序没有改变，所以插入排序是稳定的

1.4代码演示

#include<stdio.h>
#include<stdlib.h>
/*
直接插入排序：是就地排序，是稳定的，时间复杂度：O（n^2） 
*/ 
int a[105]; 
int n;
int main()
{
	int t;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	//认为：a[1] 是有序区域，a[2---n]是乱序区
	for(int i=2;i<=n;i++)
	{
		t=a[i];
		int j;
		for(j=i-1;j>=1;j--)
		{
			if(a[j]>t)
			{
				a[j+1]=a[j];
			 } 
			 else{
			 	break;
			 }
 
		}
		a[j+1]=t;
	 } 
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

2.折半插入排序

折半插入排序是一种插入排序算法，通过不断地将数据元素插入到合适的位置进行排序，在寻找插入点时采用了折半查找

2.1基本思想

折半插入排序的基本思想是：顺序地把待排序的序列中的各个元素按其关键字的大小，通过折半查找插入到已排序的序列的适当位置。
从名字就能看出来，运用了二分查找的插入排序。在上面标准的插入排序算法中，我们会将待插入关键字 key = arr[i] ，然后在数组 [0，i - 1] 的范围内查找待插入关键字 key 的正确位置，这里的查找操作的时间复杂度为O(n)量级。但是如果使用二分查找在数组 arr 的 [0,i - 1] 的范围内查找关键字 key ，那么就可以将查找操作的时间复杂度降到O(logn)量级

2.2性能

折半查找只是减少了比较次数，但是元素的移动次数不变。折半插入排序平均时间复杂度O(n^2)；空间复杂度为O(1)；是稳定的排序算法

3.2-路插入排序算法

二路插入排序算法是在折半排序的基础上对其进行了改进，减少其在排序过程中移动记录的次数从而提高效率。
具体实现思路为：另外设置一个同存储记录的数组大小相同的数组 d，将无序表中第一个记录添加进d[0]的位置上，然后从无序表中第二个记录开始，同 d[0] 作比较：如果该值比d[0] 大，则添加到其右侧；反之添加到其左侧。其实就是对于环形数组的插入

4.希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

4.1基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap =gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量

原始数组以相同的颜色为一组

初始增量gap=length/2=5，意味着整个数组被分为5组，[8,3],[9,5],[1,4],[7,6],[2,0]。

然后我们对这5组分别进行直接插入排序，结果就变成

可以看见例如3，5，6这些小元素就在前面了，然后缩小增量gap = 5/2 = 2，将数组分成两组

 对以上的两组再分别进行直接插入排序，结果如下。此时整个数组的有序程度就更近一步了

 再缩小增量，gap=2/2=1.此时整个数组为1组。[0,2,1,4,3,5,7,6,9,8]

 此时，只需要对以上数列简单微调。无需大量的移动操作即可完成整个数组的排序

4.2 性能

希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2...1}(希尔增量)，其最坏时间复杂度依然为O(n2)。这是为什么呢？
到底什么地方出了问题呢？我们再来看一个坏的例子，假设这是我们的初始序列，如果用shell的增量序列我们会一开始怎么做呢？这一共有16个数字

我们一开始就做8间隔的排序，8间隔的排序我们就从1开始，然后往后数7个数字，就是排1和5，发现本来就是有序的，什么都不用动，然后下一个，就是9和13，也是有序的，2和6，还是有序的，10和14还是有序的，继续往后看，就会发现，我做了一个8间隔的排序，结果哪个元素都没有动，大家保持原样的走下来了，下一步我要做4间隔的，结果还是全部都是有序的。
结果这趟白跑了，2间隔的排序，你应该猜到结果了，还是什么都没干，最后要达到有序，还是得靠我们1间隔的排序。结果这趟白跑了，2间隔的排序，你应该猜到结果了，还是什么都没干，最后要达到有序，还是得靠我们1间隔的排序。所以这其实是一个让人非常囧的情况，就是前面我白做了3趟排序，然后最后还是跟原始的插入排序一样，还不如一开始我就直接做原始的插入排序，那到底什么地方出了问题呢？我们通过仔细的分析会发现因为它的增量元素不互质，8是4的倍数，4是2的倍数，2是1的倍数，那么小的增量就有可能在后面的排序里面根本不起作用

4.3Hibbard增量序列

4.4更多的增量序列

4.5代码演示

#include<stdio.h>
#include<stdlib.h>
/*
希尔排序：取希尔增量序列时： 是就地排序，不是稳定的，时间复杂度：O（n^2）
*/ 
int a[105]; 
int n;
int main()
{
	int t;
	scanf("%d",&n);
	int k=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int d=n/2;d>=1;d=d/2)  
	{
		k++;//计算趟数 
		//以增量d分组，对每组进行直接插入排序
		for(int i=1+d;i<=n;i++)
	    {
	    	t=a[i];
	    	int j;
	    	for(j=i-d;j>=1;j=j-d)
	    	{
	    		if(a[j]>t)
	    		{
	    			a[j+d]=a[j];
				}
				else{
					break;
				}
			}
		     a[j+d]=t;	
		 } 
		 
		 printf("第%d趟，增量为%d,排好的结果：",k,d);
		for(int i=1;i<=n;i++)
		{
		printf("%d ",a[i]);
		}
		printf("\n");
	 } 
 
	return 0;
}

三.交换排序

1.冒泡排序

1.1算法思想

 第二步，比较 5 和 4，5 > 4，交换 5 和 4 的位置：

 第三步：比较 5 和 2 ，5 > 2，交换 5 和 2 的位置：

 第四步：比较 5 和 8 ，5 < 8 ，不交换

 第五步：比较 8 和 4 ， 8 > 4，交换 8 和 4 ：

此刻我们获得数组当中最大的元素 8 ，使用橘黄色进行标记：
第一轮冒泡结束，最大的元素8到了最后，然后对于前面5个元素，进行第二轮冒泡最终结果：

事实上第二阶段结束，整个数组已经有序了，但是对于冒泡排序而言并不知道，她还需要通过第三阶段的比较操作进行判断。
对于冒泡排序算法而言，她是通过判断整个第三阶段的比较过程中是否发生了交换来确定数组是否有序的，显然上面的过程中没有交换操作，冒泡排序也就知道了数组有序，整个算法执行结束

1.2关于冒泡的优化

基本的冒泡排序的实现方式，就是两个for循环，持续比较和交换。这种实现方式有一个明显的弊端，就是不论数组是否有序，两层 for 循环都要执行一遍，而我们是希望数组有序的时候，仅进行一轮判断，或者一轮都不进行（当然不判断，排序算法是不能知道数组是否有序的）

一次优化

这里我们增加了一个标识数组是否有序 ，当冒泡排序过程中没有交换操作时， swapped =false ，也意味着数组有序；否则数组无序继续进行冒泡排序。不要小看这个变量，因为这个变量，当数组有序的时候，冒泡排序的时间复杂度将降至 (因为其只需要执行一遍内层的 for 循环就可以结束冒
泡排序)，没有这个变量，数组有序也需要的时间复杂度

二次优化
一次优化是为了避免数组有序的情况下，继续进行判断操作的。那么二次优化又为了什么呢？
我们看下面的例子

经过一次冒泡后，我们会注意到一个问题，但是我们注意到，数组数组中的 [5,6,8] 本身已经有序，而对于有序的部分进行比较是没有意义的，相当于在白白浪费资源，有没有什么办法减少这样的比较次数呢？换句话说，是否能够确定出已经有序部分和无序部分的边界呢？
答案当然是肯定的，这个边界就是第一趟冒泡排序的过程中最后一次发生交换的位置 j ：也就是1 和 4 发生交换之后，4 和 5 没有发生交换，此时 1 之后的元素为有序。

第一步：4 和 2比较，4 > 2 ，交换 4 和 2 ，将 LastSwappedIndex = 0 ；

第二步：4 和 1 比较，4 > 1，交换 4 和 1， LastSwappedIndex = 1 ；
第三步：比较 4 和 5 ， 4 < 5，不交换， lastSwappedIndex 也不更新;
第四步：比较 5 和 6 ，不交换， lastSwappedIndex 也不更新;
第五步：比较 6 和 8 ，不交换， lastSwappedIndex 也不更新;
第一趟冒泡排序结束了，这里似乎看不出和之前有什么区别，但是来看第二趟冒泡排序就不一样了，此时 j 的 取值将从 j = 0 到 j = lastSwappedIndex ，第一步：比较 2 和 1 ，2 > 1，交换， lastSwappedIndex = 0 ，并且第二趟冒泡也就结束了，也就说我们节省了 从 2 到 6的比较操作；
最后再来一趟冒泡排序，发现没有任何交换，所以冒泡排序结束。
相比于一次优化的实现方式，二次优化的实现方式进一步减少了不必要的执行次数，两种优化后的实现方式需要冒泡排序的趟数是一样的，本质上没有什么区别。所以即使对于一个有序的数组，两种方式的时间复杂度都是O（n）

1.3复杂度分析

时间复杂度：
最坏情况下（数组逆序）：
当 i == 0 的时候，j 的取值范围是从 0 到 n -1，内循环的执行判断和交换操作 n - 1 次；当 i == 1的时候，j 的取值范围是从 0 到 n -2，内循环的执行判断和交换操作 n - 2 次；以此类推......当 i 取最大值n - 2 时，j 的取值为 1，内循环的执行判断操作 1 次；所以，整体内循环的判断语句执行次数就是：1 +2 + 3 + ... + (n - 2) + (n - 1) 。则最坏情况下的时间复杂度为O（n^2）量级。
最好情况下（数组有序）：
当 i == 0 的时候， swapped = false ，j 的取值范围是从 0 到 n -1，内循环的执行判断操作 n -1次，但是没有发生交换操作，冒泡排序算法直到数组已经有序，所以执行结束。则最好情况下的时间复杂度为O（n）。

空间复杂度：
冒泡排序没有使用任何额外的空间，空间复杂度为 O（1），是典型的原地排序算法

稳定性分析：
我们可以发现，两个 4 的相对位置没有发生变化，也就是说冒泡排序是稳定的。但这仅相当于实验验证，而在理论上冒泡排序为什么是稳定的呢？
本质原因在于冒泡排序比较和交换的是两个相邻元素，对于键值相同的关键字是不交换位置的，所以排序前后键值相同的关键字的相对位置才保持不变的

1.4如何用两个栈实现冒泡

对于这个问题本身，你可能会觉得没有任何意义，但是当你去努力实现的时候，就会发现，你对于栈和冒泡排序的理解有了新的见解。
问题本身不难理解，就是利用两个栈，然后每一次选择出数组中最大的元素，并存入数组对应的位置。但是当你自己去实现时，还是会发现好多问题，比如如何互换着使用两个栈？如何对栈中相邻的两个元素比较大小，并交换位置？
下面是参考的思路：
给定两个栈 s1 和 s2 ，以及一个长度为 n 的数组 arr :
1、将数组 arr 中的所有元素压入栈 s1 当中；
2、执行 for 循环 n 次（每一次选择出一个最大的元素）：
1. 情况一： s1 不为空， s2 为空，则尝试将栈 s1 当中的所有元素压入栈 s2 ，并保证 s2的栈顶元素为最大值；当 s1 为空时， s2 中的栈顶元素即为栈中元素的最大值，插入数组相应位置。
2. 情况二： s2 不为空， s1 为空，则尝试将栈 s2 当中的所有元素压入栈 s1 ，并保证 s1的栈顶元素为最大值；当 s2 为空时， s1 中的栈顶元素即为栈中元素的最大值，插入数组相应位置。

1.5详细解析

初始时两个栈 s1 和 s2 都为空栈，数组 arr[] = [5,1,4,2,8] 。
第一步：将数组 arr 中的所有元素都压入栈 s1 当中：

第二步：栈 s2 为空，直接将 s1 的栈顶元素 8 压入栈 s2 

第三步：栈 s1 不为空，尝试将 s1 的栈顶元素 2 压入栈 s2 ，但是此时 s2 的栈顶元素 8 >2，所以利用一个临时变量 tmp 交换两个元素在栈中的位置，先将 s2 的栈顶 8 保存到 tmp 并弹出，然后压入元素 2 ，最后再将8重新入栈。(其实就是交换操作)

 第四步：栈 s1 不为空，同第三步一样将 s1 的栈顶元素压入栈 s2 当中：

第五步：栈 s1 不为空，同上将 s1 的栈顶元素 1 压入栈 s2 当中： 

第六步：栈 s1 不为空，同上将 s1 的栈顶元素 5 压入栈 s2 当中： 

之后的过程和前面讲的类似，将栈 s2 中的元素压入栈 s1 当中，并找到次大元素 5 ，以此类推，实现对数组的冒泡排序

1.6代码演示

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
/*所谓交换,是指根据序列中两个关键字比较的结果来对换这两个关键字在序列中的位置。*/
int a[maxx],n,t;
int v;//标记 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	//冒泡排序
	//外层循环控制 排序的趟数 n个元素排序需要循环n-1次 【1】
	for(int i=1;i<=n-1;i++) 
	{
		v=0;
        //内层循环控制比较的次数 n个元素第i趟比较n-i次 【2】
        for(int j=1;j<n-i+1;j++) 
		{
            //比较相邻的元素大小 目的：将最大的元素选出到移动到最后 
            if(a[j]>a[j+1])
			{
				v=1;
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
        if(v==0)//v仍然等0，说明没交换，说明完全有序 
        {
        	break;
		}
    }
	for(int i=1;i<=n;i++)
	{
	 printf("%d ",a[i]);
	}
	return 0;
}

2.快速排序

2.1算法思想

快速排序首先选一个基准（你也可以认为是要放到排序后数组正确位置的元素）pivot，然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有很多种，所以快速排序具有很多版本。
总是选择第一个元素作为基准 pivot；
总是选择最后一个元素作为基准；（以这个举例）
随机的选择一个元素作为基准；
选择最中间的元素作为基准；
快速排序的关键是划分 partion() 。每一趟划分，我们就可以将作为 pivot 的值 x 放到排序数组的正确位置，并且将所有比 x 小的放到 x 的左边，所有比 x 大的元素放到 x 的右边。而且划分操作的时间复杂度是线性，即O（n）量级！
为了讲解快速排序并验证其稳定性，我们用下面的数组进行说明（其中两个4分别用不同的颜色标注）：

首先选择数组当中的最后一个位置元素 7 作为 pivot：然后就是执行第一趟快速排序
第一步：设置一个指针 i = -1 （初始化为 -1，用于找到 pivot 的正确位置），设置一个遍历数组的指针 j = 0 ，用于遍历从 0 到 pivot 的前一个元素 4 （即两条竖线之间的元素，从而将 7 放到排序后数组的正确位置）：

第二步：比较 j 当前指向的元素 1 和 7 ，1 <= 7 ；指针 i++ ，即 i = 0 ，交换 arr[i] 和arr[j] ，即 交换 arr[0] 和 arr[0] （数组本身并无变化） ；便利然后指针 j 向右移动：

第三步：比较当前 j 指向的元素 8 和 7 （pivot），8 > 7；什么都不做；然后指针 j 向右移动：

第四步：比较当前 j 指向的元素 3 和 7 ，3 <= 7；指针 i++ ，即 i = 1 ，交换 arr[i] 和arr[j] ，即 交换 arr[1] = 8 和 arr[2] = 3 ；然后指针 j 向右移动：

第五步：比较当前 j 指向的元素 9 和 7 ，9 > 7；什么都不做；然后指针 j 向右移动：

第六步：比较当前 j 指向的元素 4 ，4 <= 7；指针 i++ ，即 i = 2 ，交换 arr[i] 和arr[j] ，即交换 arr[2] = 8 和 arr[4] = 4 ；然后指针 j 向右移动：

第七步：比较当前 j 指向的元素 5 和 7 ，5 <= 7；指针 i++ ，即 i = 3 ，交换 arr[i] 和arr[j] ，即交换 arr[3] = 9 和 arr[5] = 5 ；然后指针 j 向右移动：

第八步：比较当前 j 指向的元素 4 和 7 ，4 <= 7；指针 i++ ，即 i = 4 ，交换 arr[i] 和arr[j] ，即交换 arr[4] = 8 和 arr[6] = 4 ；然后指针 j 向右移动：

 第九步：此时遍历结束，交换 arr[i+1] 和 arr[high] = pivot ，即交换 9 和 7

此时第一趟快速排序结束啦，我们确定了最开始选择的 pivot 的正确位置。
接下就是分别对 7 左侧比 7 小的元素 [1,3,4,5,4] ，与右侧比 7 大的元素进行快速排序，过程和第一趟排序过程一样
这里就会有一个问题，一趟快速排序结束了。就是将数组按照pivot分成了小于等于pivot的一组和大于pivot的一组，可是分治的明显么？好像不明显。
前面提到快速排序和归并排序一样均属于分治算法，而我之前在写归并排序时提到过，分治与递归就是⼀个孪生兄弟，提到了分治，怎能缺少递归呢？
递归三要素中最核心的就是确定一个函数的功能，而我们经过上面对一趟快速排序的介绍，可以发现，之后的每一趟快速排序事实上和第一趟是一样的，也就意味着反复调用同一个函数存在，即快速排序的过程中蕴含了递归思想，这也是分治的个佐证。
但是我们也可以有更清晰的解释，且看下图：

首先根据原始数组 [1,8,3,9,4,5,4,7] ，将数组划分为小于等于 7 的数组 [1,3,4,5,4] 和[8,9] ，然后将 [1,3,4,5,4] 根据 4 划分为 [1,3,4] 和 [5] ；将 [1,3,4] 根据 4 划分为[1,3] ；将 [1,3] 根据 3 划分为 [1] ；将 [8,9] 根据 9 划分为 [8] ；这个过程不就是二分吗？

的确如此，只不过对于这个数组而言选择最末尾的元素作为 pivot 得到的树的高度并不是我们期望的logn = log8 = 3 ，而是 4 说到这里，我们顺带说一下快速排序的缺点，对于一个有序数组 [1,3,4,4,5,7,8,9] 而言，如果每次选择最后一个元素作为 pivot ，就会得到下面一幅图：

而这时树的高度变成了n ，也就意味着快速排序退化成了一颗单链，这不是我们希望看到的。但是我们每一次选择最中间的元素作为 pivot ，又会怎么样呢？
如果将数组 [1,8,3,9,4,5,4,7] 重新调整顺序，使得快速排序的的分治过程如上图所示？看着图就能写出来了，当然答案可能有很多个，最简单的一个就是 [1,4,3,5,8,9,7,4] 。

2.2复杂度分析

快速排序的时间通常表示为：T(n) = T(k) + T(n - k + 1) + n
其中 T(k) 和 T(n - k + 1) 分别表示递归调用，而最后一项n表示将最后一个元素作为pivot进行划分 的处理过程，k 表示比 pivot 小的元素的数目。
而快速排序的时间复杂度取决于输入的数组和划分策略，所以需要从三个方面分析：

最坏情况：
最后情况就是我们每一次选择最大的元素或者最小的元素作为 pivot 。以我们上面讲快速排序选择做末尾的元素作为 pivot，最坏情况就是输入的待排序数组为有序数组（以升序为例），此时 k = n -1 ，那么：T(n) = T(n - 1) + T(0) + n ,即T(n) = T(n-1)+n ;所以最坏情况下的时间复杂度为O(n^2) 量级。不理解推导没关系，设对有序数组 [1,3,4,4,5,7,8,9] 进行快速排序，每次选择最末尾的元素作为 pivot，那么就会得到下图所示的情况：

也就说需要选择 n个 pivot，并且以每一个 pivot 进行划分需要O(n)的时间，那么总的时间就是O(n^2)量级

最好情况：
当划分过程中每一次都能选择最中间的元素作为基准 pivot ，那么快速排序的时间复杂度就等于：T(n) = T(n/2)+T(n/2)+n 其中T(n)表示快速排序的时间复杂度，T(n/2) 表示划分出的两个子数组排好序所用的时间， n表示将最后一个元素作为pivot进行划分函数的执行时间。
根据主定理，快速排序最好情况下的时间复杂度为 O(nlogn).
当然我们也可以换一个角度来算，比如对数组 [1,8,3,9,4,5,4,7] 而言，我们希望得到的是下面一幅图：

这个树的高度就是 O(logn)，也就是选择 pivot 需要O(logn) 次，而根据每一个 pivot 我们需要 O(n)的时间执行划分函数，所以总的时间复杂度为O(nlogn)量级。

空间复杂度分析：
快速排序的实现中，我们仅使用了一个临时变量用于交换操作，也就是其空间复杂度为O(1)，所以快速排序也是一个原地排序算法。
稳定性分析：
快速排序的划分阶段会进行交换操作，而这种交换操作会破坏原始数组中元素之间的相对位置，也就意味着，快速排序是一个不稳定的排序算法。当然所有的排序算法都可以变得稳定

2.3快速排序的稳定性从哪里来

快速排序是不稳定的。这个论述在标准的教科书上已经提了很多次，也没有什么疑问。
但是，可否通过改进的方法将其变成一个稳定的排序算法呢？
快速排序的核心过程是 Partition 函数，这个函数的作用是选择一个基准，使比之小（或等于）的数都在结果列表中处于其左边，比之大的数都在结果列表中处于其右边。我们发现，快速排序不稳定性的根源就来自于此。比如这个例子：
【1，4，2-1，3，6，2-2，5，2-3】
列表中出现了三个2，那么我们如果选择中间的2（绿色）作为基准，则第⼀次Partition结束的列表成为
【1，2-1，2-3，2-2，4，3，6，5】
或者
【1，2-3，2-1，2-2，4，3，6，5】
可见，黄色和蓝色的2都被分在了绿色2的左边或者右边，明显三个2的相对顺序变化了。
结论：如果一个数字在待排序的列表中出现三次或以上，而这个数字在列表中出现的（非首次和末次）一次被选为基准（pivot），则结果肯定是不稳定的。
因此，通过更改比较时>=符号为>符号是没有意义的，因为不稳定的根源在于基准的选取。
如果要得到稳定的快速排序，必须在选取基准时避免这种情况，而且在交换元素时要小心不要打乱相同元素的相对顺序。一种可选的做法是先记录相同元素的相对位置，再进行排序。这需要额外的空间开销

2.4代码演示

#include<stdio.h>
#include<stdlib.h>
/*交换排序：基于数据交换的排序
1.冒泡排序：是就地排序， 是稳定的，时间复杂度 O（n^2） 
2.快速排序：---递归: 是就地排序，不稳定，时间复杂度O(nlogn) ------待排序的数组已经保持需要的顺序了，容易退化成O(n^2) 
每一趟：先选一个标准（基准数），按照基准数进行划分，把比基准数小的交换到他前面，
把比基准数大的交换到他后面 
基准数怎么选：对区间(l,r) 
（1）选排序区间的第一个数--a[l]------为例 
（2）选排序区间的最后一个数--a[r] 
*/ 
void QuickSort(int a[],int l,int r)
{//选排序区间的第一个数--a[l]做基准数
   if(l>=r)
   {
   	return;
	} 
	int x=a[l];
	int i=l;
	int j=r; 
	while(i<j)
	{
		//先 从后往前，找一个小于基准数小的数，放到i位置 
		while(i<j&&a[j]>x)j--; 
		if(i<j)
		{
			a[i]=a[j];
			i++;
		 } 
		//再从前往后，找一个小于基准数大的数，放到j位置
		while(i<j&&a[i]<x)i++; 
		if(i<j)
		{
			a[j]=a[i];
			j--;
		 } 
	}
	a[i]=x;
	QuickSort(a,l,i-1); 
	QuickSort(a,i+1,r);
}
int main()
{
	int a[105]; 
	int n;
	scanf("%d",&n);
 
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
   //快速排序
   QuickSort(a,1,n); 
 
	for(int i=1;i<=n;i++)
		{
		printf("%d ",a[i]);
		}
		printf("\n");
	return 0;
}

四.归并和计数排序

1.归并排序

1.1算法思想

归并排序和之前的冒泡排序、插入排序和选择排序不同，其蕴含了一种分治的思想。
话不都说，我们还是以数组 arr = [5,1,4,2,8,4] 为例进行一趟归并排序。

第一步：计算数组的中间元素m = (l + r)/2 = 2 ，然后将数组分成[l,m]]和[m+1,r]两个区间，即[0,2]与[3,5]两个子数组，这一步属于「分」的过程

第二步：计算分出来的子数组[0,2]]的中间元素，m = (l + r)/2 = 1 ，将数组分成了[0,1]以及[2] 两个子数组，这一同样是「分」的过程，但同时也应该注意到，这一步和第一步的操作过程是一致的，也就说第一步和第二步是同一个功能，所以最终你会在代码中看到递归实现，后面会专门讲归并排序所蕴含的递归思想

第三步：将上一步分出的子数组 [0,1] 再进行拆分，m = 0 , 将数组分成了 [0] 和 [1]，只包含一个元素。 

第四步：将 arr[0] 和 arr[1] 进行合并，因为上一步得到的两个数组不可再分了，已经有序，所以进行合并。这一步事实上也是 「治」的过程，所谓治就是真正进行排序的过程，因为通过这一步元素 5和 1 的顺序将被改变

之后的每一步都是如此，我们在下图中将每一步用红色数字标注了出来：

分治和递归就像一对好基友，永远不分离，为了看到归并排序的递归过程，我们先看一下归并排序的实现。
这里的递归过程如此曲折，事实上没有什么可担心的，你将代码中的 mergeSort(arr,l,r) 理解为「分」和「递」，而将 merge(arr,l,m,r) 理解为 「治」和「归」，心中就会豁然开朗，递归与分治就是孪生兄弟。

1.2复杂度分析

时间复杂度：
归并排序（二路归并）方法就是把一个包含 n 个数的数组，折半拆分为两个子数组（二路），然后再将这两个子数组再分，一直分下去，直到分为n个长度为1的元素。然后两两按大小归并。如此反复，直到最后形成包含 n 个数的一个有序数组。
归并排序总时间 = 拆分时间 + 子数组排好序时间 + 合并时间
无论每个数组有多少个数都是折半拆分，也就是代码中的 int m = (left + right) / 2; 
所以拆分时间就常数O（1）级别，可以忽略不计。则：归并排序总时间 = 子数组排序时间 + 合并时间
空间复杂度：
在合并的时候，我们使用了存储待合并的两个数组元素的空间，这个数组大小依次开辟的就是1，2，4，8，...，n/2，但是开辟了两个，所以可能开辟的空间大小为 2，4，8，......，n，归并排序的空间复杂度为O(n)量级。与插入排序，冒泡排序，还有选择排序相比，你也可以将归并排序理解为空间换时间的有效例证。归并排序也就不是一个原地排序算法了，原地排序算法的空间复杂度为O(1).
稳定性分析：
这幅图中，可以看到归并排序是稳定的排序算法，排序前后，数组中两个4的相对位置没有发生变化。归并排序稳定的根本原因在合并的时候对值相同的两个关键字不存在交换的可能性。

1.3代码演示

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
void merge(int a[],int l,int mid,int r)
{
	//l~mid
	//mid+1~r
	int t[maxx];
	int k=0;//t数组的下标 
	int i=l;
	int j=mid+1;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			t[k]=a[i]; 
			k++;
			i++;
		}
		else{
			t[k]=a[j];
			k++;
			j++;
		}
	}
	while(i<=mid)
	{
		t[k]=a[i]; 
		k++;
		i++;
	}
	while(j<=r)
	{
		t[k]=a[j]; 
		k++;
		j++;
	}
	for(int i=0;i<k;i++)
	{
		a[l+i]=t[i];
	}
}
 
void merge_sort(int a[],int l,int r)
{
	int mid;
	if(l<r)
	{
	   	mid=(l+r)/2;
	   	//l~mid
	   	merge_sort(a,l,mid);
	   	//mid+1~r
	   	merge_sort(a,mid+1,r);
	   	merge(a,l,mid,r);
	}
	
}
int main()
{
    int n;//元素个数
	int a[maxx];// 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	 scanf("%d",&a[i]);
	}
	merge_sort(a,1,n);
 	for(int i=1;i<=n;i++)
	{
	printf("%d ",a[i]);
	}
	printf("\n");
	return 0;
}

2.计数排序

计数排序是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量（类似于哈希映射），然后对映射后的数组进行排序输出即可。（计数排序在某些情况下比快速排序还要快）

2.1算法思想

我们以数组 [1,4,1,2,5,2,4,1,8] 为例进行说明

第一步：建立一个初始化为 0 ，长度为 9 (原始数组中的最大值 8 加 1) 的数组 count[] :

 

第二步：遍历数组 [1,4,1,2,5,2,4,1,8] ，访问第一个元素 1 ，然后将数组 count[] 中下标为 1 的元素加 1，表示当前 1 出现了一次，即 count[1] = 1 ;

第三步：访问数组 [1,4,1,2,5,2,4,1,8] 的第二个元素 4 ，然后将数组 count[] 中下标为 4的元素加 1 ，表示当前访问的元素 4 当前出现了 1 次，即 count[4] = 1 ;

第四步：访问数组 [1,4,1,2,5,2,4,1,8] 的第三个元素 1 ，然后将数组 count[] 中下标为 1 的元素加 1，即 count[1] = 2 ，表示当前 1 出现了 2 次：

第五步：访问数组 [1,4,1,2,5,2,4,1,8] 的第四个元素 2 ，然后将数组 count[] 中下标为 2 的元素加 1，即 count[2] = 1 ，表示当前 2 出现了 1 次：

第六步：访问数组 [1,4,1,2,5,2,4,1,8] 的第五个元素 5 ，然后将数组 count[] 中下标为 5的元素加 1，即 count[5] = 1 ，表示当前 5 出现了 1 次：

第七步：访问数组 [1,4,1,2,5,2,4,1,8] 的第六个元素 2 ，然后将数组 count[] 中下标为 2的元素加 1，即 count[2] = 2 ，表示当前 2 出现了 2 次：

第八步：访问数组 [1,4,1,2,5,2,4,1,8] 的第七个元素 4 ，然后将数组 count[] 中下标为 4的元素加 1，即 count[4] = 2 ，表示当前 4 出现了 2 次：

第九步：访问数组 [1,4,1,2,5,2,4,1,8] 的第八个元素 1 ，然后将数组 count[] 中下标为 1的元素加 1，即 count[1] = 3 ，表示当前 1 出现了 3 次：

第十步：访问数组 [1,4,1,2,5,2,4,1,8] 的第九个元素 8 ，然后将数组 count[] 中下标为 8的元素加 1，即 count[8] = 1 ，表示当前 8 出现了 1 次：

此时遍历数组 [1,4,1,2,5,2,4,1,8] 结束，我们得到了一个 count[] 数组，而只要得到了这个 count[] 数组，我们的排序算法就相当于结束了，接下来的就只是输出了

2.2稳定性

如果不考虑计数排序的稳定性，我们按照数组 count[] 中对应下标的出现次数直接输出即可：
为了保证计数排序的稳定性，我们又该如何做呢？
先不考虑这么复杂，但是从宏观的角度来看，我们的目的就是找到待排序数组中每一个元素在排序后数组当中的正确位置。首先看一下 count[] 数组本身， 数组中的 0 对于我们的输出没有任何影
响，所以我们可以考虑将其直接去掉：

 那么此时的我们就可根据去掉之后的数组得到排序后数组的一个轮廓图：

但是这样我们并不知道相同的数字在对应原始数组 arr[] 中的哪一个元素，就相当于直接输出，而没有考虑元素的相对顺序；但是对这个过程的理解有助于我们接下来理解稳定性的处理过程。
我们看到，数组 count[] 中的每一个值表示它所对应的下标在排序后数组的出现次数，那么我们遍历数组（下标从 1 开始），并对数组 count[] 中的每一个元素执行count[i] = count[i] +count[i-1] 会得到什么呢？ 

此时得到新的 count[] 将表示他们的位置信息，比如 3 表示它的下标 1 一定出现在前 3 的位置；而紧接其后 5 则表示下标 2 出现在第 4 和第 5 个位置；下标为 3 的 count[3] = 5 ，其与前面count[2] 值相同，两者之差也就表示其出现次数，0 次，所以不占位置；下标为 4 的位置值为 7 ，则表示下标 4 出现在第 6 和 7 的位置，依次类推，你也可以对新的 count[] 数组中的每一个元素做出解释。
但我们怎么可能停留在这里呢？
有了这个新的 count[] 数组，我们如何得到元素数组 arr[] 在排序后的输出数组 output[]中的正确位置呢？
回答了这个问题，稳定的计数排序也就彻底理解了
第一步：从后向前遍历，具体为什么是从后向前，看完了你就会明白了！首先是 i = n-1 = 8，然后计算出 arr[i] = arr[8] = 8 在排序后数组的正确位置 count[arr[i]] - 1 = count[8] -1 = 8 ，即排序后arr[8] 的正确位置为 8 ，然后将 arr[8] 赋值给 output[8] = 8 ，但是count[arr[8]] = count[8] 减 1 ：

第二步： i = n - 2 = 7 ，然后计算 arr[7] = 1 在排序后数组的正确位置 count[arr[7]] - 1 = count[1] - 1 = 2 ，即最后一个 1 在排序后的正确位置下标为 2 ，然后将 count[arr[7]]的值减 1 。这里为什么要减 1 ，因为我们已经找到了最后一个 1 的正确位置，目前就剩余两个 1 没有找到正确位置。

 依次类推，我们就可以得到arr[]中每一个元素在排序后的正确位置

这就是稳定的计数排序，那我们再来回答一下为什么从后向前遍历新的 count[] 数组？
因为只有这样才能保证计数排序的稳定性！比如原始数组 arr[] 中 3 个 1 的在排序后的相对位置就没有发生变化，依旧保持：
可是问题又来了，如果我们的数组变成了 arr[] = {-1,4,1,-2,5,-2,4,-1,8} ，上面介绍的计数排序的实现方式不就出现了问题吗？因为数组下标也没有负数的情况呀！很简单，将最小元素映射到下标为0的位置。其他元素依次映射。
我们只需要找到数组 arr[] = {-1,4,1,-2,5,-2,4,-1,8} 中的最小值 min = -2 ，以及最大值 max = 8，然后开辟一个大小为 max - min + 1 的 count[] 数组，统计出数组当中每一个元素出现的次数即可，就像下面这样： 

其中数组 arr[] 的最小值 min = -2 ， -2 被映射到了 count[] 数组下标为 0 的位置，原数组中包含 2 个 -2 ，所以 count[0] = 2 ；原数组 arr[] 当中有 3 个 -1 ，其中 -1 - (-2) = 1 ，也就说 -1映射到了 count[] 数组下表为 1 的位置，所以 count[1] = 3 

2.3复杂度分析

时间复杂度：
在整个代码实现过程中，我们仅仅出现了一层的 for 循环，没有出现任何 for 循环的嵌套，所以计数排序的时间复杂度为O（n）量级。
空间复杂度：
由于计数排序过程中，我们使用到了一个 max - min + 1 大小的 count[] 数组，所以计数排序的空间复杂度为O（n）量级。
优缺点分析：
1. 如果输入数据的范围 range = max - min + 1 不明显大于要待排序数组的长度 n = arr.length ，则计数排序是相当高效的，比时间复杂度为 的快速和归并排序都优秀。
2. 计数排序不是基于比较的排序算法，时间复杂度为 ，空间复杂度与数据范围成正比。
3. 计数排序通常用作另一个排序算法（例如基数排序）的子过程。
4. 计数排序可以使用部分哈希在O（1）的时间内统计数据的频率。
5. 计数排序适用于负输入。
6. 计数排序不适用于小数的情况。

3.桶排序

3.1桶排序的思想

其实桶排序重要的是它的思想，而不是具体实现，桶排序从字面的意思上看：
1、若干个桶，说明此类排序将数据放入若干个桶中。
2、每个桶有容量，桶是有一定容积的容器，所以每个桶中可能有多个元素。
3、从整体来看，整个排序更希望桶能够更匀称，即既不溢出(太多)又不太少。
那么这些个桶跟排序有什么关系呢？我们先来看桶排序的定义

工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响

 简单点说：
1、将代排序的序列部分分到若干个桶中，每个桶内的元素再进行个别的排序。
2、时间复杂度最好可能是线性的O（n），桶排序不是基于比较的排序
当然，桶排序是一种用空间换取时间的排序

既然是排序，那么最终的结果肯定是从小到大的，桶排序借助桶的位置完成一次初步的排序——
将待排序元素分别放至各个桶内。
而我们通常根据待排序元素整除的方法将其较为均匀的放至桶中，如 8 5 22 15 28 9 45 42 39 19 27 47 12 这个待排序序列，假设放入桶编号的规则为： n/10 。这样首先各个元素就可以直接通过整除的方法放至对应桶中。而右侧所有桶内数据都比左侧的要大

在刚刚放入桶中的时候，各个桶的大小相对可以确定，右侧都比左侧大，但桶内还是无序的，对各个桶内分别进行排序，再依次按照桶的顺序、桶内序列顺序得到一个最终排序的序列

3.2关于桶排序的算法分析

上面讲了桶排序的具体思想，但是你是不是总觉得心理没那么踏实呢，这就完了？总觉得怪怪的是吧？
桶排序确实有很多不一样的地方，无论是算法时间复杂度还是整个算法的流程，都不如啥快排、归并这些传统排序来的实在。
桶排序的时间复杂度到底是多少？
我们假设有 n 个待排序数字。分到 m 个桶中，如果分配均匀这样平均每个桶有 n/m 个元素。首先在这里我郑重说明一下桶排序的算法时间复杂度有两部分组成：
1.遍历处理每个元素，O(n)级别的普通遍历
2.每个桶内再次排序的时间复杂度总和
对于第一个部分，我想大家都应该理解最后排好序的取值遍历一趟的O(n);而第二部分咱们可以进行这样的分析：
如果桶内元素分配较为均匀假设每个桶内部使用的排序算法为快速排序，那么每个桶内的时间复杂度为 (n/m) log(n/m) 。有m个桶，那么时间复杂度为 m * (n/m)log(n/m) = n (log n-log m) .在这里如果到达极限情况 n=m 时。就能确保避免桶内排序，将数值放到桶中不需要再排序达到O(n)的排序效果,当然这种情况属于计数排序

3.3桶排序适用情况

桶排序并且像常规排序那样没有限制，桶排序有相当的限制。因为桶的个数和大小都是我们人为设置的。而每个桶又要避免空桶的情况。所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀，又要要求桶的设计兼顾效率和空间。
桶排序的适用场景非常明了，那就是在数据分布相对比较均匀或者数据跨度范围并不是很大时，排序的速度还是相当快且简单的

但是当数据跨度过大时，这个空间消耗就会很大；如果数值的范围特别大，那么对空间消耗的代价肯定也是不切实际的，所以这个算法还有一定的局限性。同样，由于时间复杂度为 O(n+m)，如果 m比 n 大太多，则从时间上来说，性能也并不是很好。但是实际上在使用桶排序的过程中，我们会使用类似散列表的方式去实现，这时的空间利用率会高很多，同时时间复杂度会有一定的提升，但是效率还不错。我们在开发过程中，除了对一些要求特别高并且数据分布较为均匀的情况使用桶排序，还是很少使用桶排序的，所以即使桶排序很简单、很快，我们也很少使用它。
桶排序更多地被用于一些特定的环境，比如数据范围较为局限或者有一些特定的要求，比如需要通过哈希映射快速获取某些值、需要统计每个数的数量。但是这一切都需要确认数据的范围，如果范围太大，就需要巧妙地解决这个问题或者使用其他算法了

4.基数排序

与基于比较的排序算法（归并排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基于比较的排序算法的时间复杂度最好也就是O（nlogn），而且不能比 O（nlogn）更小了。
计数排序的时间复杂度为O（n）量级，更准确的说，计数排序的时间复杂度为O（n + k），其中k表示待排序元素的取值范围（最大与最小元素之差加 1 ）。
那么问题来了，当这个元素的的范围在 1 到 n^2 怎么办呢？
此时就不能用计数排序了奥，因为这种情况下，计数排序的时间复杂度达到了O(n^2)量级。
比如对数组 [170, 45, 75, 90, 802, 24, 2, 66] 这个而言，数组总共包含 8 个元素，而数组中的最大值和最小值之差为 802 - 2 = 800 ，这种情况下，计数排序就 ”失灵了“ 。
那么有没有那种排序算法可以在线性时间对这个数组进行排序呢？
答案就是今天要讲的基数排序 。基数排序的总体思想就是从待排序数组当中，元素的最低有效位到最高有效位逐位进行比较排序；此外，基数排序使用计数排序作为一个排序的子过程。
下面我们就以数组 [170, 45, 75, 90, 802, 24, 2, 66] ，学习基数排序！

4.1算法思想

数组当中的最大值802为三位数，所以我们在不足三位的数字前面补 0 ，即 [170, 045, 075, 090, 802, 024, 002, 066] 方便后续说明基数排序

第一步：按数组当中元素的最低有效位，个位 [170 ,045 ,075 , 090 ,802 , 024 , 002 , 066 ]，进行计数排序：

 第二步：按数组当中元素的次最低有效位，十位数 ，进行计数排序：

 

 第三步：按数组当中元素的最高有效位，百位，进行计数排序：

 

 这样我们就完成了基数排序，得到了一个有序数组 [2, 24, 45, 66, 75, 90, 170, 802]

4.2复杂度分析

时间复杂度：
设d表示输入的数组当中最大值的位数（比如 802，3位，d = 3 ），那么基数排序的时间复杂度就是 O(d x (n+b))，其中n表示数组的长度，而b则是表示一个数的基础，对十进制而言 b = 10 ；
设K是一个计算机可表示的最大整数，那么d = log以b为底K ；则基数排序整个时间复杂度为O( (n+b) X log以b为底K) 。对于一个较大的数 K，计数排序的这个时间复杂度似乎比基于比较的排序算法都慢，但是事实未必。
假设 K <= n^c取一个最大整数，其中c是一个常量；
那么基数排序的时间复杂度就为 O( c X (n+b) X log以b为底K) ，其中b 和 c都是常数，我们可以忽略不计，那么基数排序的时间复杂度就变成了O( nX log以b为底n) ，但是这依旧不比基于排序算法的最好时间复杂度 O(nlogn)好呀？
可是当我们将这个b取足够大呢？ b取多少的时候基数排序的时间复杂度才能变成线性呢

当b = n 的时候， ，logn为底n = 1,基数排序的时间复杂度就变成了O(n) ，线性时间复杂度。也就说，当数字用n进制表示的时候，我们就可以对 1 到n^c 范围之内的数组进行线性排序。对于元素的跨度（范围）比较大的数组而言，基数排序的运行时间可能比快速排序要好。但是对于基数排序而言，其渐近时间复杂度中隐含了更高的常量因子，并非完全的线性；而快速排序更有效地利用硬件缓存，提高其效率。此外，基数排序使用计数排序作为子过程，计数排序占用额外的空间来对数组进行排序。
但是基数排序解决我们最开始所提出的问题，当数据范围在 1 到 n^2 时，计数排序的复杂度将变
为O(n^2)量级，而基数排序依旧可以在线性时间进行排序！

空间复杂度：
计数排序使用了额外的空间进行排序，空间复杂度为 O(n)

五.选择排序（二叉堆）

1.堆

堆是一类基于完全二叉树的特殊数据结构。通常将堆分为两种类型： 1、大顶堆（Max Heap）：在大顶堆中，根结点的值必须大于他的孩子结点的值，对于二叉树中所有子树都满足此规律 2、小顶堆（Min Heap）：在小顶堆中，根结点的值必须小于他的孩子结点的值，对于二叉树中所有子树都满足此规律

 小顶堆就是以任意一个结点作为根，其左右孩子都要大于等于该结点的值，所以整颗树的根结点一定是树中值最小的结点，而大顶堆正好特性相反

2.二叉堆

二叉堆是满足下面属性的一颗二叉树：

1、二叉堆必定是一颗完全二叉树。二叉堆的此属性也决定了他们适合存储在数组当中。
2、二叉堆要么是小顶堆，要么是大顶堆。小顶二叉堆中的根结点的值是整棵树中的最小值，而且二叉树中的所有顶点及其子树均满足这一特性。大顶堆与小顶堆类似，大顶堆的根结点的值是整棵树中的最大值，而且二叉树中所有结点的值也均大于等于其子树结点。
由于小顶堆和大顶堆除了在顶点的大小关系上不一致，两者均是一颗全完二叉树，下面的所有讲解，都以小顶堆为例进行说明，会了小顶堆，大顶堆你自己都能写出来。

3. 二叉堆的存储结构

二叉堆是一颗完全二叉树，一般用数组表示。其中根元素用 arr[0] 表示，而其他结点（第 i个结点的存储位置）满足下表中的特性：

二叉堆的这种表示方式和性质其本质上与一颗完全二叉树自身所具有的特性一一对应

4. 小顶二叉堆常见的操作

获得元素/根元素：
获取小顶二叉堆的根元素 getMin() 按照上面的存储结构，根结点为 arr[0] ，返回即可。
移除最小元素
移除小顶二叉堆的最小元素 removeMin() ，因为移除小顶二叉堆的最小元素（即堆顶元素）之后，需要对堆进行调整，从而使得堆依旧维持其属性，一般将调整的过程称为堆化 。
我们以下图为例进行说明：

 删除堆顶元素 10 ，然后将最后一个元素 50 作为小顶堆的堆顶：

然后从堆顶元素 50 开始进行堆化。
第一步：计算当前堆顶元素 50（i = 0） 的左孩子 l = arr[2 * i + 1] = arr[1] = 15 ，以及右孩子 l = arr[2 * i + 2] = arr[2] = 20 ，然后比较三者，选择出三者的最小值 15 ，将 15和 50 进行交换，继续对值为 50 的顶点（i = 1）的子树进行堆化： 

第二步：计算当前要进行堆化的结点 50（i = 1） 的左右孩子，左孩子 l = arr[3] = 45 ，右孩子不存在，比较 50 和 45 ，发现 50 > 45 ，交换两者，然后继续对值为 50 的顶点（i = 3）的子树进行堆化：

第三步：计算要进行堆化的结点 50 (i = 1) 的左右孩子，发现不存在，所以结点 50 已经到叶子结点，整棵树堆化完成啦（其实这个堆化的过程还是挺简单的，我们后面删除等还会用到堆化的）。

更新给定下表的值
这里有一个假设是 new_val < val 的值，如果 new_val > val ，那么就是对更新的结点进行堆化，所以就不单独进行处理。还想两种都处理，加个 If...else... 就可以啦。这个操作和堆化的操作相反，我们是从被更新的结点开始向上回溯，直到结点的值大于父结点的值停止

我们将下标为 4 的结点 50 的值更新为 8 ：
第一步：判断结点 8（i = 4） 的父结点 15（ i=(4 - 1)/2 = 1 ） 的大小关系，8 < 15 ，交换 8 和 15 ，然后结点 8（i = 1） 继续做判断：

第二步：判断结点 8（i = 1） 与其父节点 10（ i=(i - 1)/2 = 0 ）的大小关系，8 < 10 , 交换 8 和10 ：

第三步：判断结点 8（i = 0），发现其本身已为根结点，没有父结点，更新结束

插入结点
插入结点 insert() ：将一个新结点插入到树的末尾，如果新结点的值大于其父结点的值，插入就直接完成了；否则，类似于 updateKey() 操作，向上回溯修正堆。
比如，还是刚才的图，我们插入结点 30（i = 5） ，由于其值大于父结点的值 20 ，并没有违反堆的属性，直接插入完成。

在插入结点 30 的基础上，我们再插入结点 9（i = 6） ：

新插入结点的值 9（i = 6）小于父结点 20（i = 2） 的值，故交换结点 9 和 20 ，然后继续判断值为 9（i = 2） ：

判断结点 9（i = 2） 与其结点 10（i = 0） 的值， 9 < 10 ，交换 9 和 10 ，然后继续判断值 9（i = 2） ：

发现值 9（i = 2） 已经是根结点了，插入完成 

删除结点

删除结点 delete() : 删除一个结点的时间复杂度也是 。将要删除的结点用无穷小 INT_MIN 替换，即调用 updateKey(i, INT_MIN) ; 然后再将堆顶元素 INT_MIN 移除，即调用 removeMin() 

比如，我们删除结点 15（i = 1），第一步，调用 update(1, INT_MIN) 将该结点的值替换为INT_MIN :

 第二步：调用 removeMin() 函数将 INT_MIN 移除即可

5.简单的选择排序与堆排序代码演示

 简单的选择排序

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
int a[maxx],n,t;
int minn; 
int main()
{
    int minn;//最小元素的下标 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	 scanf("%d",&a[i]);
	}
	//简单选择排序:就地排序， 时间复杂度O(n^2) ,不稳定的排序 
	//简单选择排序:进行n-1趟排序，每次都在乱序区中选择一个最小的元素，放在乱序的第一个位置，此时有序区+1，乱序区-1 
	for(int i=1;i<=n-1;i++)//控制循环趟数
	{
		minn=i; 
		for(int j=i+1;j<=n;j++)//控制乱序区，去找最小的元素的位置
		{
			if(a[j]<a[minn])
			{
				minn=j;
			}
		}
		//把minn位置的元素放在乱序区的第一个位置，即i位置
		if(minn!=i)
		{
		int t=a[i];
		a[i]=a[minn];
		a[minn]=t; 
		}	
	 } 	 
	for(int i=1;i<=n;i++)
	{
	printf("%d ",a[i]);
	}
	printf("\n");
	return 0;
}

堆排序

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
/*升序排列 
   堆排序:就地排序，不稳定 ，时间复杂度O(nlogn) 
   n个元素，保存在a数组中，直接在a数组中
1.初始化成一个小顶堆：
  下标最大的内部节点的下标是几？最后一个内部节点的下标是几？
        n/2
（1）找到最后一个内部节点（n/2）,依次调整每棵子树
        调整过程：依次向下比较调整：若该节点比左右孩子节点中的最小值大，进行交换，直到不满足该条件位置
2.在小顶堆的基础上，进行堆排序
   循环n-1次：
  （1）输出（删除）根节点；
   （2）最后一个位置的节点代替根节点
（3）向下调整
---输入最后一个元素
3.堆中插入一个元素：
（1）把元素放到数组最后
（2）向上和父亲节点比较进行调整
  
 */
void downAdjust(int a[],int i,int m)//对以 下标i的元素 为根节点的子树进行向下调整 
{//now是当前调整的节点，next是now的孩子，也是下一次要调整的节点 
	int now=i;
	int next;
	int t;
	while(now*2<=m)
	{
		next=now*2;//now的左孩子
		if(next+1<=m&&a[next+1]<a[next])
		{
			next=next+1;//now的右孩子 
		}
		if(a[now]<=a[next])
		{
			break;
		 } 
		 else{
		 	t=a[now];
		 	a[now]=a[next];
		 	a[next]=t;
		 	now=next;
		 }
	 } 	 	
}
void upAdjust(int a[],int n)
{//now是当前调整的节点，next是now的父亲，也是下一次要调整的节点
	int now=n;
	int next; 
	int t;
	while(now>1)
	{
		next=now/2;// now的父亲
		if(a[next]<=a[now])//父亲节点比当前节点大 
		{
			break;
		}
		else
		{
			t=a[now];
		 	a[now]=a[next];
		 	a[next]=t;
		 	now=next;
		}
	} 		
} 
int main()
{
    int n;//元素个数
	int a[maxx];// 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	 scanf("%d",&a[i]);
	}
//把a数组初始化成小顶堆
	for(int i=n/2;i>=1;i--)
	{
		downAdjust(a,i,n);
	 } 
//堆排序
    int m=n;
    int t;
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[1]);
		t=a[1];
		a[1]=a[m];
		a[m]=t;
		m--;
		downAdjust(a,1,m);
 	} 
 	printf("\n");
 	for(int i=1;i<=n;i++)
	{
	printf("%d ",a[i]);
	}
	printf("\n");
//在堆中插入一个元素；
	n++;
	scanf("%d",&a[n]);
	upAdjust(a,n);
	return 0;
}
//堆的应用--优先队列 

---

总结

一般算法竞赛时直接用sort()函数就可以解决排序问题啦，这里的诸多排序方法我们需要掌握思想就好啦！