【数据结构】——八大排序（详解+图+代码详解）看完你会有一个全新认识

创作不易，给一个免费的三连吧？！ 

 

前言

排序在生活中是非常重要的，所以排序在数据结构中也占有很大的地位，相信大家可能被这些排序弄得比较混淆或者对某个排序原理没有弄清，相信看完本篇会对你有所帮助！

排序的概念与应用

排序概念

排序：排序就是使一串数据，按某个或者某些关键字的大小，递减或者递增排列起来的操作

稳定性：在排序的过程中，可能存在两个或者以上的关键字相等的记录，排序的结果可能会不一样，这里就分成了稳定和不稳定。稳定就是指如果有两个相等的关键字设置为 r1,r2,没有排序的时候，r1在r2的前面，排完以后r1还是在r2的前面，这个排序就是稳定的，反之就是不稳定的（比如1 2 3 5 5，排完以后可能后面的5换到了前面5的前面）

内排序：就是把全部的数据元素放在内存中进行排序；

外排序：数据元素太多不能同时放在内存中，整个排序的过程需要在内外存之间进行多次交换数据才能进行

排序应用

 排序的分类

下面给出排序算法的代码声明

//插入排序
void InsertSort(int* a, int n);
//希尔排序
void ShellSort(int* a, int n);
//冒泡排序
void BubbleSort(int* a, int n);
//选择排序
void SelectSort(int* a, int n);
//双指针快排
void QuickSort(int* a, int left,int right);
//霍尔快排
void HuoerSort(int* a, int left, int right);
//挖坑法
void HoelSort(int* a, int left, int right);
//堆排序
void HeapSort(int* a, int n);
//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp);
//计数排序
void CountSort(int* a, int n);
 

排序算法实现

1.插入排序

void InsertSort(int* a, int n);

插入排序思想 ：把要排序的数，从后往前去插入，插入完后保持有序，知道所有数插入完成，得到一个新的有序序列

 这其实就是和你打扑克摸牌一样

1.1. 直接插入排序

在插入第i个元素时，前面的i-1个元素都已经有序，这个时候，把a[i]这个元素和前面a[i-1],a[i-2]...a[0]，进行比较，找到合适位置将其插入，这个时候把后面的元素往后面移动一位就行。

如果考虑最坏的情况则插入的数都要移到到最前面，然后整体往后移，所以时间复杂度为

O(N^2)

 空间复杂度为

O(1)

如果元素越接近有序，那么这个算法的时间效率也就越高。

因为在插入的过程中不会导致相同元素的相对位置发生改变，所以这种算法是稳定的

代码实现

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;//一开始第一个元素肯定是有序的，所以不用管
		int tmp = a[i + 1];//这里表示第二个元素，开始从后往前插入
		while (end >= 0)
		{
			if (tmp < a[end])//这里排升序。
			{
				a[end + 1] = a[end];//如果要插入的数，比前一个数小
                                    //插入到这个数的前面时，要往后移动一个单位
				end--;
			}
			else
			{
				break;//如果比它大直接退出
			}
		}
		a[end + 1] = tmp;//然后在end+1的位置插入这个数
	}
}

 这里用图来说明

 可以很清楚的看到，在比较完以后，插入的位置是end+1。这里的排序是排好了一部分的，其实完整的应该是从只有一个数据开始排，这里这样操作可以更好的理解这一步的操作

1.2 希尔排序

希尔排序就是对直接插入排序的升级和改良。

希尔排序的基本思想：先对序列进行预处理，使得它接近有序，然后进行直接插入排序，最后变成有序序列

前面就说了直接插入排序对于有序序列的插入效率是很高的，所以希尔排序的速度就会很快

它的整体思想就是取一个整数，把这个序列分成几个组，所有距离为这个整数的序列分在这个组里面，然后分别对这些序列进行插入排序，然后让这个整数减小，再分组，减小再分组，最后当这个整数变为1的时候，也就变成了插入排序

可能这样还是比较难以理解，可以结合下面的图进行推理

从图中可以看出，如果一直往后面走，这个序列会越来越接近有序，最终完成有序

由于它的时间涉及到一个“增量”序列的函数，所有它的时间复杂度非常难计算，这里只能模糊说明一下，在开始的时候由于取的间距比较大，然后比较和交换的次数不是很多，随着这个间距缩小，会导致所需要的时间越来越多，但是后面由于基本有序，用的时间又会越来越短

由此我们可以大概得出时间复杂度为

O(n^3/2)

空间复杂度为

O(1) 

由于它一直在交换，很容易导致前后位置发生改变所以它是一个不稳定的排序

代码实现

 

void ShellSort(int* a, int n)
{
	int gap = n;//先对其赋值
	while (gap > 1)
	{
		gap = gap / 3 + 1;//然后进行缩小，也可以是gap/=2
                          //这里的+1是为了防止出现gap==0的情况
		for (int i = 0; i < n - gap; i++)//i<n-gap，是为了防止越界
		{
			int end = i;
			int tmp = a[end + gap];//后面的操作跟直接插入排序差不多，
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;//这里不是-1，是-gap
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序和直接插入排序的代码非常像，可以去对比理解 

 2.交换排序

2.1  冒泡排序

冒泡排序非常容易理解，不想上面的希尔排序，有点复杂

冒泡的思想就是，两两交换，进行一轮以后最大的数就到了最后面去了，然后一直重复，直到把所有的数全部排好

时间复杂度

O(N^2)

空间复杂度

O(1)

在交换的过程中，如果两个数相等，那么不交换，所有他们的相对位置没有发生改变，所有冒泡是一种稳定的排序 

代码实现

void BubbleSort(int* a, int n) 
{
	for (int i = 0; i < n; i++)
	{
		int falg = 1;//
		for (int j = 1; j < n - i; j++)
		{
			if (a[j] < a[j - 1])
			{
				
				int tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
				falg = 0;
			}
		}
		if (falg)//如果是有序，那么就不用比较了，直接跳出
			break;
	}
}

2.2  快速排序

 快速排序有三种版本

1.hoare

2.双指针

3.挖坑

这三种版本只是代码实现不同，时间效率上都是一样的

快排的基本思想：

在一个序列里，先选出一个数，把大于这个数的放在这个数的右边，小于的放在这个数的左边，因为后面的操作和这里重复，所以这里选择用递归去完成

因为这里的操作和二分有点像，所以时间复杂度大致为

O(NlogN)

空间复杂度为

O(1) 

由于是不断交换位置，所以相对位置也是难以保证的，所以快排是一个不稳定的排序 

代码实现，这里直接给出三个版本以及思想

1.hoare 大致为两边向中间靠近，先选一个key,设置两个指针，一个prev在key的位置，一个cur在最后的位置，一开始cur先走，寻找比key小的，找到以后，prev后走去寻找比key大的，两个都找到以后然后交换，最后两个指针相遇，然后交换prev位置和key位置的值，最终完成一遍，然后再去递归key左边和key右边

下面给图来理解

 由图我们可以去写出代码

void HuoerSort(int* a, int left, int right)
{
	if (left >= right)//递归条件
		return;
	int keyi = left;
	int begin = left, end = right;//这里用设置前后位置
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])//这里的>=是为了防止如果是相等的数，那么就会死循环
                                                   //这里的left<right为了防止数组越界
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])//和上面一样
		{
			left++;
		}
		Swap(&a[right], &a[left]);//找到了就交换
	}
	Swap(&a[left], &a[keyi]);//这里也可以是right和keyi进行交换，都一样
	keyi = left;。交换以后记得把keyi更新，以便后面的递归
	HuoerSort(a, begin, keyi-1);//左边递归
	HuoerSort(a, keyi + 1, end);//右边递归
}

 从图中我们可以发现左边的都是小于key的，右边的都是大于key的，可能有的人会疑惑为啥与key交换的就是比key小的！！

其实可以这样想，cur要一直找到小于key的才停下，所以如果是prev遇到cur，那么也是小于key的，第二种情况就是cur停止了，prev也停止了，那么两个交换，prev的位置的值就是小于key的，那么cur继续走遇到prev那么也就是小于key的，所以这个恒成立

2.双指针

这里的双指针就是一前一后的指针，和上面不一样，一个是在开头一个是在末尾

基本思想都差不多，这个虽然表现形式不一样，但都是把小于key的值丢到左边，大于的丢到右边，然后递归进行下去直到完成

下面给出图，有助于理解

根据上面的图，我们可以写出代码

void QuickSort(int* a, int left,int right)
{
	if (left >= right)
		return;
	int perv = left, cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			perv++;
			Swap(&a[cur], &a[perv]);//无脑交换就行
		}
		cur++;//cur继续走
	}
	Swap(&a[perv], &a[keyi]);走到结束的时候，交换
	keyi = perv;
	QuickSort(a, left, keyi-1);//递归去实现左边
	QuickSort(a, keyi + 1, right);//递归右边
}

 3.挖坑法

挖坑法也是开头一个指针，末尾一个指针，然后先选择一个坑，然后把这个坑的n值保留起来，右边开始找小于key的值，找到了就把这个值丢到这个坑里面，然后自己形成新的坑，然后左边也是一样，多说无益，直接上图

根据图可以写出代码

void HoelSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = a[left];
	int hoel = left;
	int begin = left, end = right;//这里就是把开始的位置记下来，然后用left，right去走
	while (left < right)
	{
		while (left<right && a[right]>=key)//这里的条件和第一个方法一样的道理
		{
			right--;
		}
		a[hoel] = a[right];
		hoel = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hoel] = a[left];
		hoel = left;
	}
	a[hoel] = key;
	HoelSort(a, begin, hoel -1);，hoel的位置就是最后坑的位置，然后递归左边和右边
	HoelSort(a, end, hoel + 1);

以上就是交换排序了，快排掌握一种就行，这里建议是双指针，因为其他细节处理比较多，容易出错 ，但是画图去写还是可以的，三种效率没有差别，只是表现形式不一样

3.  选择排序

3.1 简单选择排序

 这里的简单现在排序，经典的就是选一个最小数，然后把它和第一个交换，然后一直遍历就行，这里比较好理解，就直接上代码了。

但是这里对它进行一些优化，在遍历数组的时候，选一个最小的，选一个最大的，分别放在头和尾，然后再选次大和次小的，虽然有点优化，但是这对整体的影响很小，不能根本上改变简单选择排序效率问题

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;，
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if(a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		int tmp1 = a[mini];//最小的值和第一个元素交换
		a[mini] = a[begin];
		a[begin] = tmp1;
		if (begin == maxi)//这里是怕如果begin和maxi重合了，由于上面已经和最小的交换了
                          //那么后面如果直接交换就会出问题，所以特判一下
		{
			maxi = mini;
		}
		int tmp2 = a[maxi];//最大的值和最后一个元素交换
		a[maxi] = a[end];
		a[end] = tmp2;
 
		end--;//交换以后区间缩小，然后继续选数
		begin++;
	}
}

时间复杂度

O(N^2) 

空间复杂度

O(1) 

因为选择排序可能会导致前后的相对位置改变，所以它是不稳定的排序

比如5 5 1 1，a[2]与a[0]交换，那么5 5的相对位置就改变了

3.2  堆排序

对于堆排序，在之前的文章已经说明了原理，这里就不再说明了，想看原理可以去看这篇博客

这里简单说一下，如果想排升序那么建大堆，想排降序，建小堆，然后建堆向下调整就可以完成排序

这里直接给出代码

 

void AdjustDown(int* a, int n, int parent)//向下调整，我们需要的是最后的父亲结点，所以传父亲过来
{
	int child = parent * 2 + 1;//孩子左边运算的公式
	while (child < n)
	{
		if (child+1<n&&a[child + 1] > a[child])//判断
		{
			child++;
		}
		if (a[child] > a[parent])这里是建大堆
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

由于向上调整的时间复杂度比向下调整要高所以我们都采用向下调整算法，也就是说我们建堆和排序都用向下调整就可以搞定

时间复杂度

O(NlogN) 

空间复杂度

O(1) 

 堆排序这样交换，肯定是不稳定的

4. 归并排序

归并排序和快速排序有点像，归并排序就是分成两个区间，然后一直分直到分成1个数一个区间的时候，这个时候就是有序的了，因为一个数就是有序的