【数据结构】--八大排序算法【完整版】_数据结构排序

本文主要讲解代码及代码思路，涵盖八大排序的全面知识点

————————————————

目录

一、直接插入排序

二、希尔排序(直接插入排序的改良版)

三、选择排序（直接选择排序）

四、堆排序

五、冒泡排序

六、快速排序

1、 左右指针法

2、挖坑法：

3、前后指针法：

4、快速排序的非递归实现

七、归并排序

1、归并排序的递归实现

2、归并排序的非递归实现

八、计数排序

九、总结：

---

排序概念： 

排序 ：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

数组中相同值，排完序相对顺序可以做到不变就是稳定的，否则就不稳定。

稳定性还是重要的，因为比如考试中给班级前三名同学颁发奖品，如果现班级前几名分数依次为100,99,96,96,96,那三个96我们肯定认为谁先交谁就是第三名，如果这个排序稳定，那就是公平的，如果不稳定，就可能造成不公平，后交的变成了第三名。

那么判断这个排序是否稳定可以看如果数组中有相同值，相同值会不会换，主要依靠的就是对应排序的思想。

内部排序 ：数据元素全部放在内存中的排序。

外部排序 ：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

一、直接插入排序

void InsertSort(int* a, int n)
{   //加一个for循环就成了复合排序
	for (int i = 0; i < n - 1; i++)
	{
		//单趟排序
        //把下标为end+1的数据插入到下标为[0,end]的有序区间
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

1、单趟排序的原理 

 原理：在数组前面已经是升序下，插入一个数据，让数组重新变为升序该怎么做。

2、整体复合排序

原理：既然单趟排序是利用已存在升序原理做的。那我们就对整个数组从头开始都假设升序然后插入一个数据。

3、直接插入排序的时间复杂度和空间复杂度：

时间复杂度：O(N*N)

插入排序的时间复杂度可以通过分析算法的执行过程来计算。在最坏的情况下，即待排序的数组是逆序排列的情况下，插入排序需要比较和移动元素的次数最多。

假设待排序数组的长度为 n。在插入排序中，我们从第二个元素开始，依次将每个元素插入到已排序的子数组中。为了将当前元素插入到正确的位置，我们需要将其与已排序子数组中的元素进行比较，并移动比它大的元素。

在最坏情况下，每个元素都需要与其前面的所有元素进行比较，并且可能需要移动整个已排序子数组。因此，对于第 i 个元素，需要比较 i-1 次，并且可能需要移动 i-1 次。

假设移动一个元素需要花费 O(1) 的时间，比较两个元素也需要花费 O(1) 的时间。在最坏情况下，对于第 i 个元素，我们需要比较和移动 i-1 次。所以总的时间复杂度可以表示为：

T(n) = 1 + 2 + 3 + ... + (n-1) = (n-1) * n / 2 = O(n^2)

因此，插入排序的时间复杂度为 O(n^2)。需要注意的是，这只是最坏情况下的时间复杂度，而在最好情况下，即数组已经是有序的情况下，插入排序的时间复杂度为 O(n)。

空间复杂度:  O(1) 

稳定性：稳定 因为排序完数组中相同的值相对位置不变

---

二、希尔排序(直接插入排序的改良版)

1、希尔排序概念

希尔排序法又称缩小增量法。希尔排序法的基本思想是： 先选定一个间距gap，把待排序数据中所有数据分成个 组，所有距离为gap的记录分在同一组内，并对每一组内的数据进行排序。然后，重复上述分组和排序的工 作。直到当gap =1 时，再排序，排完就有序了 【 注意：gap是组内每个数据的间隔 】

 2、为什么要引入希尔排序？

在直接插入排序的基础上进行优化，效率更高，如果数据很多，我们是需要这个效率的

那直接插入排序的效率：顺序有序最好O(N) ，逆序最坏，越接近有序，效率越好。

但直接插入排序本身并不知道数组是有序还是逆序，效率有不确定性，在此之上，希尔提出了优化的方式。

3、希尔排序：

①、预排序（使数组接近有序）:gap>1用来预排序，因为预排序后基本就会接近有序

②、直接插入排序：预排序后gap=1用来直接插入排序。

把间距为gap的值分为一组，进行插入排序

gap越大，前面大的数据可以越快到后面，后面小的数，可以越快到前面，但gap越大，越不接近有序。

gap越小越接近有序，当gap=1时其实就相当于直接插入排序，就有序了。

大体步骤： 

 

对于一组的预排序应该如下：

            int end //这里应该是一组中待插入数据前面那个数据的下标;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;

多组并排（希尔排序完整代码）：

void ShellSort(int* a, int n)
{
	assert(a);
	//1、gap>1相当于预排序，让数组接近有序
	//2、gap==1相当于直接插入排序，保证有序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//+1保证了最后一次一定是1，因为一个数一直/3一定会有0
		//gap==1最后一次就相当于直接插入排序
		for (int i = 0; i < n - gap; i++)//加上for循环可以实现多组并排
		{
			//进行直接插入排序
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
 
}

对于多组并排我们想的肯定是一组一组排序，但人们之前就想到更好的代码，可以一下把所有间距为gap的所有组的排序都排完，从end=0开始，排的是一组，排完后end++排的可能就是另一组，因为有间距gap。（循环条件 i < n - gap,每次循环再i++ 就可以实现一趟把所有组都排一遍，最后end会=n-1-gap，这正是最后一组数据的倒数第二个元素，那此时插入完最后一组的最后一个数据a[end+gap]后，所有组数据就排完了 ）

理解为什么循环条件i < n - gap就可以实现把所有组排一遍了：

问题解释：

①、for循环的添加可以实现从一组的预排序到多组的排序

②、gap每次循环 gap = gap / 3 + 1是经过测试和预算，针对各种场景基本最佳的代码，有利于预排序排成有序，当然有的人会用gap /= 2，但没有gap = gap / 3 + 1优化 ,gap不断缩小的目的是为了更加有序，因为更加有序的直接插入排序效率高。

③、循环进行条件是gap > 1，gap > 1就会进行预排序，gap=1本质上就是直接插入排序，而gap=1一定会进行一次的，因为gap=gap/3+1

 希尔排序的时间复杂度：

希尔排序的时间复杂度不好计算，因为 gap的取值方法很多，导致很难去计算，希尔排序的时间复杂度并不固定

时间复杂度为O(N^1.3 ~ N^2)，一般情况下优于插入排序，但在本来有序的情况下插入排序就比希尔排序效率高，但这种情况很少。

空间复杂度：O(N)

稳定性：不稳定

---

三、选择排序（直接选择排序）

思想：

我们一般用的是一次选出一个最大值或最小值，但我们可一次选出两个值，一个最大值，一个最小值来提高效率（最小值放在第一位，最大值放在最后一位）。选出两个值后左右指针begin++,end--即可，用来忽视上一次选出的最大值和最小值，在新的区间再次找最大值和最小值，并再次将最大值放开头，最小值放末尾......

问题：

如果最大值一开始就在区间的开头，而每次区间的最小值都会放到开头的，可最大值在最小值放在开头后，还要放到末尾，可此时最大值已经被覆盖，他被换到了a[minimal]的位置了（因为Swap(&a[begin], &a[minimal]);），所以如果begin==maximal(即最大值一开始在开头)，maximal应=minimal 

 下列代码中Swap函数是利用指针交换两个元素

void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int maximal = begin, minimal = begin;
		for (int i = begin + 1; i <= end; i++)
		{//一次选出区间内最大的一个和最小的一个
			if (a[i] > a[maximal])
			{
				maximal = i;
			}
			if (a[i] < a[minimal])
			{
				minimal = i;
			}
		}
		//交换的是两者本身，并不是仅仅交换值那么简单
		Swap(&a[begin], &a[minimal]);//最小值放区间开头
		if (begin == maximal)
		{//如果一开始就相等，那么a[maximal]会=a[minimal]，会影响后续
		//maximal的使用，但是此时maximal是=minimal的，即下标相等
		//就是最小值会把最大值覆盖，而最大值后面还要用
			maximal = minimal;
		}
		Swap(&a[end], &a[maximal]);//最大值放区间末尾
		begin++;
		end--;
	}
}

时间和空间复杂度：

时间复杂度：O（N^2）

因为第一次需比较n-1次，第二次n-3，第三次n-5次以此类推，就是个等差数列，利用等差数列前n项和公式就知道为O(N^2) 

但是直接选择排序的效率不是很高，不管数组如何都会那么排，对于巧合，比如本就是升序的情况，还是会那么排，实际应用中我们不常使用

空间复杂度：O（1）

稳定性：不稳定

---

四、堆排序

 堆排序在我的另一篇博客堆的讲解中有详细讲过，这里不过多赘述

【数据结构】堆的实现（向下调整和向上调整法）和堆排序的实现_堆的调整算法-CSDN博客

 

//向下调整算法。前提:左右子树都是小堆
void AdjustDown(int* a, int n, int root)
{
	//找出左右孩子中小的那一个，默认认为左孩子是小的那一个，否则就加以调整即可
	int parent = root;
	int child = parent * 2 + 1;//先默认child是左孩子，我们的目的是让child成为小的那一个
	while (child < n)
	{//当孩子的下标<n的时候才会一直比较交换，越界就说明堆构建完了
		if (child + 1 < n && a[child + 1] < a[child])//判断还要有一个只有左子树的情况
		{//如果右孩子比左孩子还小，就让child变成右孩子,即小标+1即可
			child++;
		}
		//如果孩子小于父亲就交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;//进行下一次的比较判断
			child = parent * 2 + 1;
		}
		else
		{
			break;//因为孩子已经>=父亲了，满足小堆的条件了，就无须继续往下判断，
			//因为在调整的过程中可能就存在在越界之前，孩子>=父亲的情况
            //谨记向下调整法用于只有堆顶不满足，而左右子树满足堆的性质的时候使用
		}
		//仅交换一次还不能够满足小堆，应该持续比较并交换，所以应该是个循环
	}
 
}
 
//堆排序
void HeapSort(int* a, int n)
{
	//1、数组建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	//当然i也可初始化为n-1,即从叶子结点开始调，但是这么做肯定没有从叶子结点
	//的父节点开始调高效
	}
	//2、找次小，排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		
		//再继续选次小的
		AdjustDown(a, end, 0);
		--end;
//没有真的删除最后一个数据，只是说我下次再找小交换，最后一个数据
//不被看作堆里面的，不造成影响
	}
}

时间和空间复杂度：

堆排序使用堆来选数，效率就高了很多。

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定

---

五、冒泡排序

冒泡和快速排序都是交换排序 

交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，其特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动 

思路：

比较基础，两个两个比，最后把最大的放最后（或把最小的放最前）即可。但有一种情况:如果在第一次比较中，一次都没交换说明已经有序了，故利用标志性flag来判断是否有序

 

 
void BubbleSort(int* a, int n)
{
    assert(a);
	int i = 0;
	int flag = 0;
 
    //有n个元素的数组进行n-1次排序即可
	for (i = 0; i < n-1; i++)
	{
		int j = 0;
 
        //一次冒泡排序
		for (j = 0; j < n - i - 1; j++)
		{//假设一次冒泡排序找最大的那个数
			if (a[j] > a[j+1])
			{
				Swap(&a[j], &a[j+1]);
				flag = 1;
			}
		}
 
        //flag==0说明本来就有序，一次交换都没有，就不用往下进行了
		if (flag == 0)
		{
			break;
		}
	}
}

时间复杂度和空间复杂度：

时间复杂度：O（N^2）

n-1+n-2+n-3+......还是一个等差数列，所以是O (N^2)

空间复杂度:O（1）

稳定性：稳定

---

六、快速排序

快速排序分为单趟排序和整体排序

单趟排序有三种方法：

1、左右指针法

2、挖坑法（左右指针法的变形）

3、前后指针法

三种方法只是写法上的差异，性能没有差别

1、 左右指针法

单趟排序的思路（假设排升序，n为数组元素个数）：

选定一个基准值（数组中的值）Key，通常会选第一个值或最后一个值都可以，然后会设置两个值begin=0，end=n-1，即begin和end都为数组元素下标，begin从左往右走，end从右往左走，begin找比Key大的值(a[begin])，end找比Key小的值(a[end])，（若begin和end遇到和Key相等的值，要继续走，因为与Key相等的值在Key的左边还是右边无所谓，但主要因为没这个条件，begin和end就无法往下走）且会一直找，end和begin找到后两者(a[begin]和a[end])交换即可，一直找并交换，直到begin和end重合，再把key与两者重合的那个值交换，交换后key的左边就是比key小的，右边就是比key大的。

要点：

①、左边要比Key要小，右边比Key大

②、Key要放到他正确的位置（最终要放的位置）

③、Key设置为第一个值还是最后一个值的区别仅在于begin先走还是end先走

选取最后一个数为基准值，则一定要begin先走，因为左边先走能保证最后落的位置比Key要大（然后key会与重合位置交换），因为我们想让在Key右边的值都比Key大，而begin就是用来找比Key要大的，在最后一次要重合时，begin停下来的位置一定比Key要大，而end受到循环条件begin<end的束缚，即使找不到<=Key的，最后也会落到和begin相同的位置

选取第一个数作为基准值，则一定要end先走，因为右边先走能保证最后落的位置比Key要小，因为我们想让在Key左边的值都比Key小，而end就是用来找比Key要小的，在最后一次要重合时，end停下来的位置一定比Key要小，而begin受到循环条件begin<end的束缚，即使找不到>=Key的，最后也会落到和end相同的位置

若不这么做，就可能导致Key的右边存在比Key小的，Key的左边存在比Key大的

图解左右指针法的单趟排序的过程 ：

问题解决：

代码中begin和end走的前提是begin<end，因为可能begin和end都重合了，可能end还在往左走或begin还在往右走从而导致又不重合了，但我们要保证他们第一次重合后就不要再走了，因为此时的Key与重合位置一交换他左边一定比他都小，右边一定比他都大，已经可以了。故加个条件begin<end的前提下，两者才可移动。

int PartSort(int* a, int begin, int end)
{
	int Keyindex = end;//若最后一个值为基准值
	while (begin < end)
	{
		//begin找比Key大的值，目的是放在Key的右边
		while (begin < end && a[begin] <= a[Keyindex])//等于放在Key的左边或右边均可
		{//这里一定要有=的判断条件，因为没=的话，循环不进行，begin和end都不动
		//而begin<end，就会造成死循环，反之，这里有=才行
			++begin;
		}
		//end找比Key小的值，目的是放在Key的左边
		while (begin < end && a[end] >= a[Keyindex])
		{
			--end;
		}
		
		Swap(&a[begin], &a[end]);
	}
 
	Swap(&a[begin], &a[Keyindex]);//重合位置和基准值换，这里用a[end]也可
 
	return begin;//返回相遇的位置的下标，方便实现下一次的单趟排序
}

整体排序的思路（类似于二叉树的前序遍历）：

  单趟排序后，只要Key的左边和右边都有序了，整体是不是就是有序了。那Key的左边和右边要有序，可以再选一次Key1再次单趟排序，使Key1左边的都<Key1，Key右边的都>Key1，然后此时若Key1左边的有序，右边的也有序，整个就有序了，那对于Key右边的同理，选一个Key2再次单趟排序，而对于Key2本身的左边和右边又可以选一次Key3，不断递归下去，终止条件就是划分的只剩一个值了，一个值我们就可认为是升序了，就不用再往下划分了，直接递归往回返就能实现升序，即整体排序完毕。

void QuickSort(int* a, int left, int right)
{
	assert(a);
	//递归终止的情况是left==right这是只有一个值情况下一定可为升序
	//还有一种就是left>right这个区间越界了也要结束
	if (left >= right)
		return;
 
	int div = PartSort(a, left, right);
	//[left,div-1] div [div+1,right]
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
 
	//也可以这么写
	//if (left < right)
	//{
	//	int div = PartSort(a, left, right);
	//	//[left,div-1] div [div+1,right]
	//	QuickSort(a, left, div - 1);
	//	QuickSort(a, div + 1, right);
	//}
 
}

快排的时间复杂度和空间复杂度分析：

 时间复杂度最好的情况下是每次选的key都是中位数，而单趟排序的时间复杂度是O（N）（要看它的思想，不用看代码），因为begin往右走，end往左走，最后重合，相当于把整个数组走了一遍，所以为O（N）

 时间复杂度最好的情况下：

 时间复杂度最坏的情况下：

 空间复杂度：O（logN） (以2为底，N的对数)

因为递归调用的空间复杂度是计算它的深度（每一层都要建立栈帧，而栈帧是要消耗空间），因为类似二叉树，故深度就可算出来。

缺陷：

实际当中无法保证选key是中位数，但我们可以考虑至少不要选到最大的或者最小的做key，当有序的情况下（一定是最坏的情况下），选到最大的或最小的值作为key效率不高，这种是运气很不好的情况下，一般的情况下都还很不错的。但严重的问题是面对有序的情况下需要建很多栈，而栈的空间本来就不大，堆的空间才大，如果数据很多就会导致栈溢出，程序崩溃，怎么解决呢？

三数取中：保证不要选到最小或者最大，让有序时变成最优。（即三个数中找中间数）

 即最中间的数和最大的数和最小的数选择那个最中间的数作为key，但我们之前写的逻辑都是最后一个数作为key的，那就再把这个最中间的数和最后一个数换一下就行了。

意义：让原来不是二分->利用三数取中趋近二分->效率提高

int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else //a[begin] > a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])//a[mid]是最小的，此时看a[begin]和a[end]大小关系就知道谁是中间的
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
 
}

 三数取中只要在PartSort中改一下即可，三数取中让最坏的情况不再出现，时间复杂度不再看最坏，综合而言快排时间复杂度:O（N*logN）

int PartSort(int* a, int begin, int end)
{
	//三数取中进行优化
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);
 
	int Keyindex = end;//若最后一个值为基准值
	while (begin < end)
	{
		//begin找比Key大的值，目的是放在Key的右边
		while (begin < end && a[begin] <= a[Keyindex])//等于的话放在Key的左边或者右边都是可以的
		{//这里一定要有=的判断条件，因为没=的话，循环不进行，begin和end都不动
		//而begin<end，就会造成死循环，反之，这里有=才行
			++begin;
		}
		//end找比Key小的值，目的是放在Key的左边
		while (begin < end && a[end] >= a[Keyindex])
		{
			--end;
		}
		
		Swap(&a[begin], &a[end]);
	}
 
	Swap(&a[begin], &a[Keyindex]);
 
	return begin;//返回相遇的位置的下标，方便实现下一次的单趟排序
}

2、挖坑法：

跟左右指针法的思路差不多，也可以说比左右指针法好理解那么一点点

具体思路：

先利用三数取中方法把中间的数放在最后面

1、先将选定的基准值(最右边)直接取出，然后留下一个坑， 
2、当左指针遇到大于key时，直接将该值放入坑中，而左指针指向的位置形成新的坑位，
3、然后右指针遇到小于基准值的数时，将该值放入坑中，右指针指向的位置形成坑位，
4、循环上述步骤，直到左右指针相等。最后将基准值放入坑位之中。

下图中先展示不用三数取中法的过程（若用了三数取中法key应=3） 

int PartSort2(int* a, int begin, int end)
{
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);
 
	//坑（坑的意思是这位置的值被拿走了，可以覆盖填新的值）
	int key = a[end];
 
	while (begin < end)
	{
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//左边找到比key大的填到右边的坑，begin位置就形成为了新的坑
		a[end] = a[begin];
 
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		//右边找到比keng小的填到左边的坑，end位置就形成为了新的坑
		a[begin] = a[end];
	}
	a[begin] = key;//因为begin和end相遇了，最后停的位置肯定就是坑
 
	return begin;
}

3、前后指针法：

代码简单，但不易理解。

具体思路：

1、选定基准值，定义prev和cur指针(cur = prev + 1)
2、cur先走，遇到小于基准值的数停下，然后将prev向后移动一个位置
3、将prev对应值与cur对应值交换
4、循环上面的步骤，直到cur出了数组范围
5、最后将基准值与++prev的对应位置交换
6、递归排序以基准值为界限的左右区间

最终代码改的就是PartSort3而已，QuickSort引用PartSort3函数 

int PartSort3(int* a, int begin, int end)
{
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);
 
	int cur = begin;
	int prev = begin - 1;//不能给-1，因为begin不一定就是1，快排分区间的时候begin会有变化
	int keyindex = end;
 
	while (cur < end)
	{//循环判断条件为什么没cur==end的条件呢？
	//cur==end的话，完全没必要交换，没必要执行if中的语句
	//没必要多执行一次,当然cur<=end也行，不影响结果
 
		//若++prev==cur，交不交换都行，但是最好不交换
		//即使++prev==cur,prev也会++，因为这条判断语句执行过了
		if (a[cur] < a[keyindex] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
 
		//不管a[cur]和a[keyindex]的关系如何，cur都会往后走
		cur++;
	}
	Swap(&a[++prev], &a[keyindex]);//cur走到最后只需++prev和keyindex交换即可
 
	return prev;
}

 快排的一些优化：

在递归中，若递归到后面已没什么数据了，而你还在一直递归找key值往下划分，这样就会效率低下，而且建的栈也相对多了一些。

小区间使用插入排序排，不再使用快速排序的递归排，减少整体的递归次数。

void QuickSort(int* a, int left, int right)
{
	assert(a);
	//递归终止的情况是left==right这是只有一个值情况下一定可为升序
	//还有一种就是left>right这个区间越界了也要结束
	if (left >= right)
		return;
 
	if ((right - left + 1) > 10)
	{//若在[left,right]间的数据个数>10,用快排效率高
		int div = PartSort3(a, left, right);
		//[left,div-1] div [div+1,right]
		QuickSort(a, left, div - 1);
		QuickSort(a, div + 1, right);
	}
	else
	{
		//小于等于10个以内的区间，不再递归排序，用插入排序
		InsertSort(a + left, right - left + 1);
	}
 
}

4、快速排序的非递归实现

非递归的意义：

1、提高效率（递归建立栈帧还是有消耗的，但对于现代计算机，这个优化微乎其微，可以忽略）

2、递归最大的缺陷：若栈帧的深度太深，可能导致栈溢出，因为系统栈空间一般不大，再兆(M)级别，数据结构栈模拟非递归，数据是存储在堆上的，堆是G级别的空间。

非递归的实现思路：

用栈来保存需要排序的左右区间，那肯定是先用左，再用右，那就要利用栈先进后出的性质，先利用的肯定是后入栈。

首先跟递归一样利用单趟排序，利用那三种方法哪种都行，所谓递归无非就在于他把区间不断递归划分然后找基准值key，那就让栈来做这件事就可实现非递归。每次利用栈先进后出的性质，把区间放入栈内并从栈中取出来

void QuickSortNonR(int* a, int left, int right)
{
	//创建栈
	struct Stack st;
	StackInit(&st);
 
	//原始数组区间入栈,先入右再入左，才会先出左后出右
	StackPush(&st, right);
	StackPush(&st, left);
 
	//将栈中区间排序
	while (!StackEmpty(&st))
	{
		//如果right先入栈，栈顶为left
		left = StackTop(&st);
		StackPop(&st);
		right = StackTop(&st);
		StackPop(&st);
 
		//得到基准值
		int div = PartSort3(a, left, right);
		//经过这个步骤说明key的左边都<key，右边都>key
		//只要key左边和右边有序，整个数组就有序了
		//故还要往下划分区间，找key，跟递归思路一样
 
		// 以基准值为分割点，形成左右两部分
		//这里先入key右边的区间，再入key左边的区间
		//这样取出来就先是key左边的，再是key右边的区间
		if (div + 1 < right)
		{//如果div+1>=right，==说明就剩一个值了，不用排序了，>说明区间不可以了，也不用排了
		//入栈就说明要拿出来排，这里跟之前讲的递归终止条件差不多
			StackPush(&st, right);
			StackPush(&st, div + 1);
		}
		if (left < div - 1)
		{
			StackPush(&st, div - 1);
			StackPush(&st, left);
		}
	}
	StackDestroy(&st);//栈是动态开辟的，用完它一定要释放
}

引申的总结：

递归改非递归（所有的递归都能改为非递归）

1、改为循环（如斐波那契数列），一般一些简单的递归才能改为循环

2、栈模拟存储数据非递归

---

5、补充：竞赛中的快速排序

代码模板如下：

#include<iostream>
using namespace std;
 
const int N = 100010;
int a[N];
 
void QuickSort(int* a, int l, int r)
{
    if (l >= r) return; //如果没数或只有一个数，返回即可
 
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j)
    {
        do i++; while (a[i] < x);//先++再判断
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);//相等的值也会交换
    }
    QuickSort(a, l, j);     //递归左半边区间[l,j]
    QuickSort(a, j + 1, r); //递归右半边区间[j+1,r]
}
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
 
    QuickSort(a, 0, n - 1);
 
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
 
    return 0;
}

---

6、练习：第k个数 

 
//第k个数
#include<iostream>
using namespace std;
 
const int N = 100010;
 
int a[N];
 
int quick_sort(int* a, int l, int r, int k)
{
	//会保证第k小的数一直在递归区间中，那么当区间里只有一个数时
	//就一定是要找的数了
	if (l >= r) return a[l];
 
	//1、先快排把区间划分，使左边<=x，右边>=x
	int i = l - 1, j = r + 1, x = a[l + r >> 1];
	while (i < j)
	{
		do ++i; while (a[i] < x);
		do --j; while (a[j] > x);
		if (i < j) swap(a[i], a[j]);
	}
	//2、查找k是否<=左边个数，是则说明k在左侧，左侧递归排序找到k即可，反之在右边
	//无限夹击找到k即可
	if (k <= j - l + 1) return quick_sort(a, l, j, k);//去找左半区间的第k小
	else return quick_sort(a, j + 1, r, k - (j - l + 1));//去找右半区间中的第k小
}
 
int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
 
	printf("%d", quick_sort(a, 0, n - 1, k));
 
	return 0;
}

---

七、归并排序

归并排序的思想：

 归并排序的单趟排序的思想，合并两段有序数组，合并以后依旧有序，在有序的前提下归并一次单趟排序就有序了。

但给你一个数组你无法保证它左右两端是有序的，那就把它的左端和右端分一半（n->n/2->n/4.....直到只剩一个数），并且一直分，直到剩一个数，一个数肯定是有序的，再往回归并即可（此时满足，左端和右端有序，只有整体不保证有序就可以用归并）

整个过程：分解（递归的过程）+ 合并（递归往回退） 

 整个递归过程类似于后序遍历（左右根），不会先合并，而是会一直往下分解，直到分解到剩一个数（即分割到不可分割时）才开始合并。

归并：（和之前讲过的合并两个有序的链表思路一样），对于两个有序的区间，从两个区间开头比（两个区间begin1和begin2分别指向开头，其实就是下标），建立一个tmp数组来存储，小的数放在tmp数组中，然后对应的小的数存在的区间下标++（即begin1++或者begin2++），另一个区间不动，然后再比较，还是两个区间中小的数放入tmp中，并且下标++......一直比，直到其中有一个区间走完了，再把另一个区间的数拷贝到tmp数组的后面，即整个tmp数组就是两端区间整体有序的合并，再拷贝回a数组中即可。

那为什么需要创建额外空间tmp数组？

在归并排序算法中，我们将待排序的数组分成两个子数组，然后分别对这两个子数组进行排序，最后将两个有序的子数组合并成一个有序的数组。

在合并两个有序的子数组时，我们需要使用一个临时数组来存储合并后的结果。这是因为在合并过程中，我们需要按照一定的顺序比较两个子数组中的元素，并将较小的元素依次放入临时数组中。如果直接在原始数组中进行合并操作，可能会导致元素的位置被覆盖，从而导致错误的排序结果。

通过使用临时数组，我们可以保证合并操作不会影响到原始数组中的元素位置，从而确保排序的正确性。在合并完成后，我们再将临时数组中的元素复制回原始数组的对应位置，完成整个归并排序过程。

因此，在归并排序中建立临时数组是为了保证合并操作的正确性和稳定性。

归并排序的时间复杂度和空间复杂度：

时间复杂度：O（N*logN）

本质上就跟二叉树一样，高度logN，而每一层都是N，故为N*logN

空间复杂度：O（N）（用空间换时间）

因开辟了额外的临时空间

1、归并排序的递归实现

void _MergeSort(int* a, int left, int right, int* tmp)
{
	//只有一个元素，或区间不对则终止
	if (left >= right)
	{
		return;
	}
 
	//划分数组，每次一分为二
	int mid = (left + right) / 2;
	//左区间[left，mid]右区间[mid+1,right]，左右区间有序，才可合并
	//现他们没有序，故用子问题解决
 
	_MergeSort(a, left, mid, tmp);//划分左区间
	_MergeSort(a, mid + 1, right, tmp);//划分右区间
 
	//直到有序才开始合并有序序列
	int begin1 = left, end1 = mid;//有序序列1
	int begin2 = mid + 1, end2 = right;//有序序列2
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)//任意一个区间到头了就会结束
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
 
	//对于还剩有数的序列，它的元素加到tmp数组中
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	//将合并后的序列拷贝到原数组中
	//在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
	int j = 0;
	for (j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
}
 
void MergeSort(int* a, int n)
{
	assert(a);
	//因为需要将两个有序序列合并，需借助额外数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
 
	_MergeSort(a, 0, n - 1, tmp);
 
	free(tmp);
	tmp = NULL;
}

2、归并排序的非递归实现

归并排序的递归->非递归：可以用栈和队列，但是都不够好，因为他还有空间复杂度的消耗，这里递归改为非递归用迭代好一点。

思路：

理想情况下：

本质上gap控制的是几个数据合并，gap=1，就1个1个合。

 那么对于代码实现，区间应该如何划分？

 若用 for (int i = 0; i < n; i++)

一对就是两部分（两组）,每次都是一组一组来走，那每一组都对应一个由gap划分的区间

若为开区间则为：[i，i+gap) [i+gap，i+2*gap)

若为闭区间则为：[i，i+gap-1]   [i+gap，i+2*gap-1] 

因为我们之前写的归并代码是在闭区间的基础上写的，所以这里用闭区间的，并且我们把归并部分的代码单独放在一个函数中MergeArr以方便这里的非递归的归并。

//归并排序的非递归实现
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
	int left = begin1, right = end2;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)//任意一个区间到头了就会结束
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
 
	//对于还剩有数的序列，它的元素加到tmp数组中
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	//将合并后的序列拷贝到原数组中
	//在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
	int j = 0;
	for (j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
 
}
 
void MergeSortNonR(int* a, int n)
{
	assert(a);
	//因为需要将两个有序序列合并，需借助额外数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
 
	int gap = 1;
	
	while (gap <= n / 2)
	{//当对于这个数组来说，被分成最多的两半，即gap=n/2
 
		//对于gap=一个数时，for循环内部就能实现gap=某个数时的排序
		for (int i = 0; i < n; i += 2 * gap)
		{//每次i+=2*gap就能实现这区间内每一对的排序，且不会越界
			//[i，i+gap-1] [i+gap，i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			MergeArr(a, begin1, end1, begin2, end2, tmp);
		}
		gap *= 2;
		PrintArray(a, n);
	}
 
	free(tmp);
	tmp = NULL;
}

执行结果如下： 

 

如果把a数组的元素个数改为6，运行下代码，程序直接崩溃

 故上述代码还存在问题，当元素个数是2的倍数时才会恰好排好序，本质上是因为gap每次都能正好把区间正好分为一半，因为gap每次都*=2，所以恰好分割时正好排好序，但不是2的倍数的情况下，比如只有6个元素，最终可能左边分为4个，右边分为两个才对，但代码中我们的区间范围会产生越界等问题，所以要考虑一下。

下面说的第一个，第二个数组是因为从左到右分对，一对有两部分，每部分又称为每个组，左面的那部分为第一组，右面那部分为第二组，每一组都是gap个数据。

 

1、第一个数组越界时，第二个数组不存在，所以不用合并，第一个数组本身就是有序数组
2、第二个数组完全越界时，第二个数组依然不存在，所以不用合并
3、部分组越界时，第二个数组存在但是不完整，此时我们将第二个数组的结束位置调整为原数组末尾位置即可，让第一个数组和第二个数组合并。

//归并排序的非递归实现
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
	int left = begin1, right = end2;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)//任意一个区间到头了就会结束
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
 
	//对于还剩有数的序列，它的元素加到tmp数组中
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	//将合并后的序列拷贝到原数组中
	//在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
	int j = 0;
	for (j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
 
}
 
void MergeSortNonR(int* a, int n)
{
	assert(a);
	//因为需要将两个有序序列合并，需借助额外数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
 
	int gap = 1;
	
	while (gap < n)
	{//gap不是每次折半二分二分往下走了,<n即可
	//比如n=6，最后应该分为4个和2个为一对，此时gap=4,若用之前gap<=n/2才可进来
	//4就进不来了，所以<n即可，最后gap*2=8，循环终止，排序也完毕了
 
 
		//对于gap=一个数时，for循环内部就能实现gap=某个数时的排序
		for (int i = 0; i < n; i += 2 * gap)
		{//每次i+=2*gap就能实现这区间内每一对的排序，且不会越界
			//[i，i+gap-1] [i+gap，i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
			//3、合并时第一组就越界，则无需合并
			if (end1 >= n)
				break;
			//2、合并时只有第一组，则无需合并
			if (begin2 >= n)
				break;
			//3、合并时第二组只有部分数据，需修正end2边界
			if (end2 >= n)
				end2 = n - 1;
 
			MergeArr(a, begin1, end1, begin2, end2, tmp);
		}
		gap *= 2;
	}
 
	free(tmp);
	tmp = NULL;
}

运行结果正确： 

---

3、补充：竞赛中的归并排序

 
//归并排序
#include<iostream>
using namespace std;
 
const int N = 1e5 + 10;
 
int a[N], tmp[N];
 
void merge_sort(int* a, int l, int r)
{
	if (l >= r) return;
 
	int mid = l + r >> 1;
	//递归到不可再分
	merge_sort(a, l, mid); merge_sort(a, mid + 1, r);
	//往回并,合并两段有序区间
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
		if (a[i] <= a[j]) tmp[k++] = a[i++];
		else tmp[k++] = a[j++];
	while (i <= mid) tmp[k++] = a[i++];
	while (j <= r) tmp[k++] = a[j++];
	//把tmp中的数据放回到a数组中，便于后续操作
	for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}
 
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
 
	merge_sort(a, 0, n - 1);
 
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
 
	return 0;
}

 4、逆序对的个数

---

八、计数排序

思路：

如果能统计数组中每个数出现的次数，就能把他们排出来。

效率很高，但是如果范围很大就会很费空间。计数排序针对一些特殊场景比较适用。适用于数据范围很集中，不适用于最大值与最小值相差特别大的那种，不然动态开辟会开辟很多空间。并且只适用于整形，如果是浮点型或字符串排序，还得用比较排序。

//计数排序
void CountSort(int* a, int n)
{
	//1、确定范围,先找出最大值最小值
	assert(a);
	
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}
 
	int range = max - min + 1;//统计次数的数组的元素个数应为range
	int* countArr = (int*)malloc(sizeof(int) * range);//统计出现次数的数组
	memset(countArr, 0, sizeof(int) * range);//初始化countArr数组
 
	//统计次数
	for (int i = 0; i < n; i++)
	{//每个数出现是多少，它的相对下标就是多少（但用的是相对位置）
		countArr[a[i] - min]++;//a[i]-min表示的是相对位置
	}
	//排序
	int index = 0;
	for (int j = 0; j < range; j++)
	{
		while (countArr[j]--)
		{	//出现几次就放几个
			a[index++] = j + min;
			//因为是相对位置，所以对应数是j+min
		}
	}
 
	free(countArr);
}

计数排序的时间复杂度和空间复杂度：

时间复杂度：O（N+range）(本来为2N，故约等于N)

空间复杂度：O（range）

九、总结：

1、掌握排序的实现

2、排序的时间复杂度和空间复杂度（要理解，不要硬背）

3、稳定性

4、排序之间特性的对比

归并文件排序（了解）我的另一篇博客有写

计数排序（了解）

最后：如果想测试各大排序的效率，可以用如下代码：

// 测试排序的性能对比
void TestOP()
{
 
    srand((unsigned int)time(0));//要引用头文件<time.h>
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int)*N);
    int* a2 = (int*)malloc(sizeof(int)*N);
    int* a3 = (int*)malloc(sizeof(int)*N);
    int* a4 = (int*)malloc(sizeof(int)*N);
    int* a5 = (int*)malloc(sizeof(int)*N);
    int* a6 = (int*)malloc(sizeof(int)*N);
    for (int i = 0; i < N; ++i)
     {
         a1[i] = rand();//要引用头文件<stdlib.h>
         a2[i] = a1[i];
         a3[i] = a1[i];
         a4[i] = a1[i];
         a5[i] = a1[i];
         a6[i] = a1[i];
     }
     int begin1 = clock();
     InsertSort(a1, N);
     int end1 = clock();
     int begin2 = clock();
     ShellSort(a2, N);
     int end2 = clock();
     int begin3 = clock();
     SelectSort(a3, N);
     int end3 = clock();
     int begin4 = clock();
     HeapSort(a4, N);
     int end4 = clock();
     int begin5 = clock();
     QuickSort(a5, 0, N-1);
     int end5 = clock();
     int begin6 = clock();
     MergeSort(a6, N);
     int end6 = clock();
     printf("InsertSort:%d\n", end1 - begin1);
     printf("ShellSort:%d\n", end2 - begin2);
     printf("SelectSort:%d\n", end3 - begin3);
     printf("HeapSort:%d\n", end4 - begin4);
     printf("QuickSort:%d\n", end5 - begin5);
     printf("MergeSort:%d\n", end6 - begin6);
     free(a1);
     free(a2);
     free(a3);
     free(a4);
     free(a5);
     free(a6);
}