排序算法终极篇之手撕常见排序算法

我不是女神ヾ 2024-04-22 22:15 90阅读 0赞

![f962c7870ece464980394ff1c65e0597.gif][]

> **文章目录**
> 
> 引入
> 
> 一、插入排序
> 
> 1、1 插入排序的实现思想
> 
> 1、2 插入排序的代码实现及特点分析 
> 
> 二、希尔排序
> 
> 2、1 希尔排序的实现思想
> 
> 2、2 希尔排序的代码实现及特点分析 
> 
> 三、选择排序
> 
> 3、1 选择排序的实现思想
> 
> 3、2 选择排序的代码实现及特点分析
> 
> 四、堆排序
> 
> 五、冒泡排序
> 
> 六、快速排序
> 
> 6、1 快速排序递归形式实现
> 
> 6、2 快速排序的非递归形式实现
> 
> 6、2、1 快速排序非递归形式的实现思想
> 
> 6、2、2 快速排序非递归形式的代码实现 
> 
> 七、归并排序
> 
> 7、1 递归实现归并排序
> 
> 7、2 归并排序非递归实现 
> 
> 7、2、1 归并排序非递归形式的实现思想
> 
> 7、2、2 归并排序非递归形式的实现代码及边界处理
> 
> 总结
> 
> --------------------
> 
> **?♂️ 作者：@Ggggggtm ?♂️**
> 
> **? 专栏：数据结构与 ?**
> 
> **? 标题：排序算法 ?**
> 
>  **❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️**
> 
> ![361ce4bc1b0c40699a4740e20571fab4.png][]

> 本编文章详解常见七大大排序（**插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序、归并排序**），其中**快速排序和归并排序递归实现**是我们常见的思路，但是**非递归实现**的情况相对少见，理解起来也会有点难度，本篇文章会给出详解！

## 引入 ##

> 排序算法重要吗？排序算法有什么用呢？我给大家举一个例子先看一下：![d2d8a698fff14340adc218051811ec03.png][]
> 
> 我想网上购物是平常很常见的事情了吧。我们为了更好的选择出自己理想的物品，我们通常会根据**物品的价格或者销量等条件进行筛选**。那么这就是一个**排序**。
> 
> 还有我们经常说到的大学的好坏：![6c1753ed43fc4f0ab4a254a63a244d0c.png][]
> 
> 大学之间的排名也会是**根据很多指标进行综合排序**来定名次的。在日常生活中，用到的排序的例子还有很多很多，也间接体现出来排序的重要性。我们应该熟练的掌握常见排序的细节及其用法。![36d7779ae9d64e6f8d19fab916c64b46.png][] 上图即为我们要详解的七大常见排序，我们接下来进入整体。

## 一、插入排序 ##

### 1、1 插入排序的实现思想 ###

> 插入排序是我们在生活中经常见的一种排序。例如玩扑克牌时，我们**一张一张的抽取扑克牌，每抽取一张，我们自己会对它进行排序，放到合适的位置**。![e83021940d564cf6ae4ac3280954331e.png][]
> 
> 这也是插入排序的**基本思想**。**把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。**
> 
> 我们可结合下图理解：![8373a7b5c27a4243837c1a3f2663be00.gif][]

> 从上图中，我们再详细分析一下插入排序的实现思路：
> 
> 1.  首先第一个数据不用进行比较，当只有一个数据时，我们可以理解为是有序的；
> 2.  选取下一个数据，看是否大于前一个元素。如果大于前一个元素，我们直接可以把该数据放到前一个元素的后面。如果小于前一个元素，我们需要把前一个元素后移一位。
> 3.  每插入一个新的元素，我们需要比较的时前面已经有序的所有数据，直到找到大于前一个元素数据即可停下，否则将会放在首位。
> 4.  每插入一个元素，重复上述操作即可完成有序。
> 
> 上述即为插入排序的整个实现的过程，我们接下来看一下插入排序的代码实现。

### 1、2 插入排序的代码实现及特点分析 ###

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 (a[end] > tmp)
    			{
    				a[end + 1] = a[end];
    				end--;
    			}
    			else
    			{
    				break;
    			}
    		}
    
    		a[end + 1] = tmp;
    	}
    }

> 我们学完插入排序后不难发现，正常情况下插入排序的时间复杂度为O(N^2)。只有极少的特殊情况（有序）的实现复杂度为O（N），效率并不是太理想。
> 
> 直接**插入排序的特性**总结：
> 
> 1.  **元素集合越接近有序，直接插入排序算法的时间效率越高；**
> 2.  **时间复杂度：O(N^2)；**
> 3.  **空间复杂度：O(1)，它是一种稳定的排序算法；**
> 4.  **稳定性：稳定**
> 
> 我们还可对插入排序进行优化码？答案是可以的。下面我们看希尔排序，就是在插入排序上进行了优化。

## 二、希尔排序 ##

### 2、1 希尔排序的实现思想 ###

> 通过上述的插入排序特性**元素集合越接近有序，直接插入排序算法的时间效率越高**，我们想到：是否在对改组数据排序前进行预排序呢？通过预排序是的数组达到接近有序的状态呢？希尔排序因此诞生了。
> 
>  希尔排序法又称缩小增量法。希尔排序法的基本思想是：**先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当到达所取数=1时，所有记录在统一组内排好序**。
> 
>  具体思路可结合下图理解： ![a4f502c53c1e4aed8b9bc41a1f50c556.png][]

> 那gap的大小怎么选呢？**当gap越大时，大的数据往后跳跃的越块，但是排完后并没有那么有序。当gap越小时，大的数据往后跳跃的越慢，但是排完后相对已经很有序了**。所以在这里我们gap的取法就是从数组的大小折半开始，一直折半，直到为1时，排完后有序就停止。当然，也就可以除以3，但是要注意其中的细节，**最后一趟排序gap必为1**。
> 
> 这里就会有一些疑问：上述的每一趟以gap为一组的数据排序都是用插入排序的思想实现的，那时间复杂度不是会更高吗？我们先看希尔排序的代码实现。

### 2、2 希尔排序的代码实现及特点分析 ###

void ShellSort(int* a, int n)
    {
        //以gap为3的数据一组的预排序代码，该排序分3趟
    	/*int gap = 3;
    	for (int j = 0; j <gap; j++)
    	{
    		for (int i = j; i < n - gap; i += gap)
    		{
    			int end = i;
    			int tmp = a[i + gap];
    			while (end >= 0)
    			{
    				if (tmp < a[end])
    				{
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    	}*/
        
        //希尔排序
    	//n!=1的情况，全为预排序
    	int gap = n;
    	while (gap > 1)
    	{
    		gap /= 2;
            //同时对所有以gap为一组的进行排序
    		for (int i = 0; i < n - gap; i ++)
    		{
    			int end = i;
    			int tmp = a[i + gap];
    			while (end >= 0)
    			{
    				if (tmp < a[end])
    				{
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    		
    	}
    }

> 通过上述代码，我们这里是根据插入排序特性**元素集合越接近有序，直接插入排序算法的时间效率越高**进行的预排序。当gap为1时，代码与插入排序的代码相同，但是此时的数据已经几乎接近有序，并不需要消耗太多，时间复杂度接近O（N）。
> 
>  希尔排序的特性总结： 
> 
> 1.   希尔排序是对直接插入排序的优化。 
> 2.  当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
> 3.  希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定： ![c2f297339354443bafd8b4b0adee92d3.png][] ![62f8cb7c55434af7ae1fc4671ffe6f62.png][]
> 4.  稳定性：不稳定。

## 三、选择排序 ##

### 3、1 选择排序的实现思想 ###

> 选择排序的实现就比较简单了。选择排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。也就是我们需要进行n趟寻找，每趟去寻找未排序的最小（或最大）元素完成排序。
> 
>  我们结合下图一起理解一下：![82334b859e0741bea6afa99ce93009fb.gif][]
> 
> 我们直接看代码的实现：

### 3、2 选择排序的代码实现及特点分析 ###

void Swap(int* a, int* b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    void SelectSort(int* a, int n)
    {
    	int left = 0, right = n - 1;
    
    	while (left < right)
    	{
    		int maxi = left, mini = right;
    		for (int i = left; i <= right; i++)
    		{
    			if (a[i] > a[maxi])
    			{
    				maxi = i;
    			}
    			if (a[i] < a[mini])
    			{
    				mini = i;
    			}
    		}
    
    		Swap(&a[left], &a[mini]);
    
    		//如果左边界与最大的数重合，交换左边界与最小的值后，最大值的位置下标变为交换后的下标
    		if (left == maxi)
    		{
    			maxi = mini;
    		}
    		Swap(&a[right], &a[maxi]);
    
    		left++;
    		right--;
    	}
    }

>  **直接选择排序的特性总结：** 
> 
> 1.   直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用；
> 2.   时间复杂度：O(N^2)；
> 3.  空间复杂度：O(1)；
> 4.  稳定性：不稳定

## 四、堆排序 ##

> 堆排序，我们在之前的文章中（[重点算法排序之堆排序][Link 1]）详细讲述了其实现的细节。我们可以直接去参考学习一下。

## 五、冒泡排序 ##

> 我们之前的文章也有对冒泡排序（[冒泡排序详解][Link 2]）的详解，需要学习的也可去参考一下。

## 六、快速排序 ##

### 6、1 快速排序递归形式实现 ###

> [重点算法排序之快速排序][Link 3]详解了快速排序的三种递归实现的方法，可以直接参考学习。

### 6、2 快速排序的非递归形式实现 ###

#### 6、2、1 快速排序非递归形式的实现思想 ####

> 通过学习了递归形式实现的快速排序后，我们了解到递归实现其实就是采用了分治的思想 。但是当数据量特别大、递归层数较多时，有可能会造成栈溢出（爆栈），导致进程无法正常进行。这里也可采用小区间优化方法，但是我们想能不能**采用非递归的方式去实现快排呢？如果不递归，采用循环的方式同样不会爆栈，而且更加安全**。答案是可以的。

> 我们首先需要去分析递归方式实现快排的一些性质：
> 
>  *  每次递归前我们会先选出一个关键数据，作为我们的keyi来划分左右区间；
>  *  每次的递归是去递归的左子区间和右子区间，对左子区间和右子区间进行排序划分；
>  *  当递归到左子区间和右子区间不存在时，就停止递归；
>  *  当递归到左子区间和右子区间只有一个数据时，我们认为它就是有序的，停止递归。
> 
> 通过上面分析，我们发现每次递归都是需要明确知道左右子区间下标的。于是在这里我们 就想到如果采用非递归，我们需要把所有的左右子区间下标保存下来。对其进行划分排序倒不难，主要是怎么保存起来左右子区间的下标呢？
> 
> ![872df2828e904a70a387ace36bdcd75e.png][]
> 
> 当我们自己去画一下递归实现快排的展开图时我们会发现到，递归完左子区间才会去递归右子区间。**每递归一个区间，会划分出新的两个区间**。我们这时候想到用栈去存储区间下标。最初我们存储进去其实的下标，再去循环划分排序左右子区间，并且把左右子区间把左右子区间的下标加入栈中。**循环时，从栈中去取出下标**。当左右子区间不存在时，或者只有一个数据时，我们认为它就是有序的，不再加入栈中。直到栈为空时，循环停止。我们结合下面代码一起理解一下。

#### 6、2、2 快速排序非递归形式的代码实现 ####

int PartSort(int* a, int left, int right)
    {
    	if (left >= right)
    		return;
    
    	//int randi = left + (rand() % (right - left));
    	int midi = MidKey(a, left, right);
    	if (midi != left)
    		Swap(&a[left], &a[midi]);
    	int keyi = left;
    	int begin = left, end = right;
    	while (left < right)
    	{
    		//如果是从左边界为分界点，那么必须从右边开始找，以确定right==left的位置为较小的哪一个
    		//右边找小
    		while (left<right && a[right]>a[keyi])
    		{
    			right--;
    		}
    
    		//左边找大
    		while (left < right && a[left] <= a[keyi])
    		{
    			left++;
    		}
    
    		Swap(&a[left], &a[right]);
    	}
    
    	Swap(&a[keyi], &a[left]);
    
    	keyi = left;
    	return keyi;
    }
    void QuickSortNoCir(int* a, int left, int right)
    {
    	ST st;  //建立一个栈，这里用C语言实现，引用了已实现栈的头文件，在C++中，可直接用STL中的容器
    	STInit(&st);
    
    	STPush(&st, left);
    	STPush(&st, right);
    
    	while (!STIsEmpty(&st))
    	{
    		int right = STTop(&st);
    		STPop(&st);
    
    		int left = STTop(&st);
    		STPop(&st);
    
    		int keyi = PartSort(a, left, right);
    
    		if (keyi + 1 < right)
    		{
    			STPush(&st, keyi + 1);
    			STPush(&st,  right);
    		}
    
    		if (keyi - 1 > left)
    		{
    			STPush(&st, left);
    			STPush(&st, keyi - 1);
    		}
    	}
    
    	STDestory(&st);
    }

> 这里的一个区间的排序与递归实现的排序相同，我们在这里只不过是把它单独划分为一个函数。

## 七、归并排序 ##

### 7、1 递归实现归并排序 ###

> [重点算法排序之归并排序][Link 3] 对归并排序进行了详解，可参考学习。

### 7、2 归并排序非递归实现 ###

#### 7、2、1 归并排序非递归形式的实现思想 ####

> 归并排序的非递归实现又该怎么实现呢？当我们了解了递归实现后，递归实现是先将整个区间划分为左右两个大区间，接着不断划分子区间，直到一个区间的大小为1开始归并的。于是我们**非递归实现也可从一个区间的大小为1开始归并**。当区间为1时，也就只有一个数据就被视为有序，所以就可以开始归并。当**1个数与1个数归并完后，相当于两个数的区间是有序的，就开始归并两个数据的区间**。**以此类推，最终将整个区间归并为有序区间**。大致过程可参考下图：![aab43f0c2359483a86c146f48b19492b.png][]
> 
> 这样考虑似乎并没有什么错。但是当数组的元素个数为9个呢？我们打印出归并的区间看看：![f605d533bb964d2caadd117ff3620379.png][]
> 
> 我们发现确实有很多越界的情况。因此，我们要对越界的情况进行特殊处理。我们先来开归并排序非递归实现的代码，在对越界情况处理进行解释。

#### 7、2、2 归并排序非递归形式的实现代码及边界处理 ####

void MergeSortNoCir(int* a, int left, int right)
    {
    	int* tmp = (int *)malloc(sizeof(int) * (right - left + 1));
    	if (tmp == NULL)
    	{
    		perror("malloc failed");
    		return;
    	}
    
    	int n = right - left + 1;
    	int gap = 1;
    	while (gap < n)
    	{
    		for(int i = 0; i < n;i += 2*gap )
    		{
    			int begin1 = i, end1 = i + gap - 1;
    			int begin2 = i + gap, end2 = i + 2 * gap - 1;
    
    			if (begin2 >= n)
    			{
    				break;
    			}
    			else if (end2 >= n)
    			{
    				end2 = n - 1;
    			}
    
    			int j = 0;
    			while (begin1 <= end1 && begin2 <= end2)
    			{
    				if (a[begin1] < a[begin2])
    				{
    					tmp[j++] = a[begin1];
    					begin1++;
    				}
    				else
    				{
    					tmp[j++] = a[begin2];
    					begin2++;
    				}
    			}
    
    			while (begin1 <= end1)
    			{
    				tmp[j++] = a[begin1];
    				begin1++;
    			}
    
    			while (begin2 <= end2)
    			{
    				tmp[j++] = a[begin2];
    				begin2++;
    			}
    
    			memcpy(a + i, tmp, sizeof(int)*(end2 - i + 1));
    		}
    		gap *= 2;
    	}
    
    	free(tmp);
    }

> 在这里我们把区间的边界划分为**\[ begin1 \] \[ end1 \] - \[ begin2 \] \[ end2 \]**。首先，begin1 是不可能越界的，因为我们是把 i 的值 begin1。然后我们再分情况处理越界的问题：
> 
>  *  end1 越界，就不再动该组数据（break）；
>  *  begin2 越界，也是不再动该组数据（break）；
>  *  end2 越界，begin2 没有越界。修改end2，再归并改组数据。
> 
> 上述情况中，end1和begin2越界为什么就不在动该组数据呢？**归并的前提是该组数据有左右两个有序子区间，只有一个区间是不用归并的**。因为一但end1和begin2越界，该组数据就不能够进行归并。越界情况的数据就在原数组中没有动，也就是并没有归并到tmp数组中，所以也不用再拷贝回去。
> 
> end1越界的情况，begin2也一定越界。但是end1不越界的话，begin2也有可能越界。如果end1不越界，同时begin2也不越界，就进入到了else if (end2 >= n)的情况。所以，在这里我们发现，不用判断end1的情况也是可以的。
> 
> 我们再来看加入越界判断后的区间划分：![16aff76a54784abba7ac79d545340ebf.png][]
> 
> 通过上述划分区间，我们发现不会再出现区间越界的情况，同时也不会漏掉任何区间。

## 总结 ##

> 排序总体难度还是比较大的，也是重点掌握内容，尤其是快速排序和归并排序。在这里给大家总结出一张关于排序的表格：![88dec332892e464294f9ad80ce24f5aa.png][] 大家也可借助此表格来理解和记忆排序算法。本篇文章的讲解就到这里，希望以上内容会对你有所帮助，感谢观看ovo~

[f962c7870ece464980394ff1c65e0597.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/80ef23d04a5243ceb12d88edd25f7fbf.gif
[361ce4bc1b0c40699a4740e20571fab4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/170cabbbb8c44b4cb4b1f1387bcbb291.png
[d2d8a698fff14340adc218051811ec03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/2c0cf393547d4105ba7ed0dc877ab201.png
[6c1753ed43fc4f0ab4a254a63a244d0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/77a631c037ab4054a0207d43de4b3cd7.png
[36d7779ae9d64e6f8d19fab916c64b46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/4df16e02ed264e47a49770260ee10fb6.png
[e83021940d564cf6ae4ac3280954331e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/545308965b3d4deba294ecaf35c90bb1.png
[8373a7b5c27a4243837c1a3f2663be00.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/fda7f05e7be34e45bd157a8a1f8b8086.gif
[a4f502c53c1e4aed8b9bc41a1f50c556.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/c7de3b9821da4a8aa4d62cd6779f97e5.png
[c2f297339354443bafd8b4b0adee92d3.png]: https://img-blog.csdnimg.cn/c2f297339354443bafd8b4b0adee92d3.png
[62f8cb7c55434af7ae1fc4671ffe6f62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/6d50918771a54d04822273761b7c800e.png
[82334b859e0741bea6afa99ce93009fb.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/ba420705a2884a508425eee2885459fe.gif
[Link 1]: https://blog.csdn.net/weixin_67596609/article/details/128632980
[Link 2]: http://t.csdn.cn/1XU57
[Link 3]: https://blog.csdn.net/weixin_67596609/article/details/128524405
[872df2828e904a70a387ace36bdcd75e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/cb51f197776a43e2a3c8d71ab998ae9a.png
[aab43f0c2359483a86c146f48b19492b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/290a33fc88a849be90ebac2d52a23cab.png
[f605d533bb964d2caadd117ff3620379.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/0dd6532bfff348218a005fab93dac60c.png
[16aff76a54784abba7ac79d545340ebf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/11ca590aaa4a4a908b6d616276fcae80.png
[88dec332892e464294f9ad80ce24f5aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/6f6530e4efc7411e9e34012583bcae2f.png