重点算法排序之快速排序、归并排序（上篇）

r囧r小猫 2023-09-26 17:36 33阅读 0赞

> **文章目录**
> 
> 一、排序的概念及常见的排序算法
> 
> 二、快速排序的思想及代码详解
> 
> 2、1 快速排序的思想 
> 
> 2、2 挖坑法
> 
> 2、2、1 挖坑法实现思想
> 
> 2、2、2 挖坑法举例
> 
> 2、2、3 挖坑法代码实现
> 
> 2、3 左右指针法
> 
> 2、3、1 左右指针法实现思想
> 
> 2、3、2 左右指针法举例
> 
> 2、3、3 左右指针法代码实现
> 
> 2、4 前后指针法
> 
> 2、4、1 前后指针发实现思想
> 
> 2、4、2 前后指针法举例
> 
> 2、4、3 前后指针代码实现
> 
> 三、归并排序的思想及代码详解
> 
> 3、1 归并排序的思想实现
> 
> 3、2 归并排序的代码实现
> 
> 总结
> 
> --------------------
> 
> ## **标题：重点算法排序之快速排序、归并排序（上篇）** ##
> 
> ## **作者：@Ggggggtm** ##
> 
> ## **寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景** ##
> 
> ![76c5a476909240ce9c8ec5c8b0c115e6.png][]

## 一、排序的概念及常见的排序算法 ##

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

> 在排序中我们还经常讨论这个排序是否稳定？那到底怎么来判断一个潘旭是否稳定呢？我们先看一下排序稳定的概念。
> 
> **稳定性：**假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r\[i\]=r\[j\]，且r\[i\]在r\[j\]之前，而在排序后的序列中，r\[i\]仍在r\[j\]之前，则称这种排序算法是稳定的；否则称为不稳定的。

> 我们比较常见的排序**有六种：**插入排序、希尔排序、选择排序、堆排序、快速排序、归并排序。应用较多的，也是相对来说比较重要的有**快速排序和归并排序。**我们**本篇文章**先来详细介绍一下**快速排序和归并排序**的思想及代码详解，由于插入排序、希尔排序、选择排序相对较为简单，所以我们就不在详解。**下篇文章**会写出**堆排序**的思想及代码详解。

## 二、快速排序的思想及代码详解 ##

### 2、1 快速排序的思想 ###

> 任取待排序元素序列中的某元素作为基准值（**我们这里一般选择数组的第一个元素或者最后一个元素或者中间的元素**），将数组的**元素与基准值比较分成左、右子序列**，**左子序列中**所有元素均**小于或等于基准值**，**右子序列中**所有元素均**大于或等于基准值**，然后对左右子序列重复该过程（**递归实现排序**），直到所有元素都排列在相应位置上为止。
> 
> 我们举一个例子一起理解一下。加入我们给出如下数组：

int arr[]={49,38,65,97,76,13,27,49};

> 对上面的数组进行快排，我们按照快排的思想分为三步骤进行排序，如下：
> 
> 1.  我们**先选出基准值**，我们在这里选择数组的最左边的数。![48ab921c6ccc46a0b7954b68b0e874b8.png][]
> 2.  按照基准直对数组进行初次排序，**分成左、右子序列**。左子序列中所有元素均小于或等于基准值，右子序列中所有元素均大于或等于基准值。![cb6eb295ff964cf4ae69a45b5ba770ea.png][]
> 3.  递归排序左右子序列，当子序列中只有一个元素时我们就不在递归（递归的停止条件）。![3e677920a92d4465a6e44cbc6916c455.png][]
> 
> 当递归结束时，此时的序列已经为有序的了。我们不难发现，快速排序递归实现有序是用了**分治的思想**。我们刚开始是把一个无序的数组分成了左、右子序列数组，进而分别对左、右子序列再分，**直到分成左、右子序列只有一个数据时**（**我们可以把一个数据看成有序的）**，就不会再分。这时递归结束后就已经是有序的了。
> 
> 那么具体显现的思路有几种呢？在这里我给出三种是实现方法：**挖坑法、左右指针法、前后指针法。**

### 2、2 挖坑法 ###

#### 2、2、1 挖坑法实现思想 ####

> 我们先来了解一下**挖坑法的主要思想：**
> 
> 1.  先选出一个坑的位置（基准值），我们选择坑的位置一般会选最左边或者最右边。
> 2.  第一次排序：当我们选择坑的位置为最左边时，我们再从数组的最右边依次往前找找比基准直小的数放到坑的位置。更新坑的位置为**从右边找到比基准直小的位置**。我们再从左边依次找比基准直大的数字放到新坑的位置。反复此操作，**当左右相遇时（此时该地方为坑）**，把基准值放到坑里就行。
> 3.  递归重复第二步骤的操作达到有序。

#### 2、2、2 挖坑法举例 ####

> 通过上述思想我们举一个例子具体看一下怎么实现的。我们给出如下数组：

![a329dd95da894bbb8bf1b9802a28b9f6.png][]

> 我们按照上述挖坑法思想来看一下具体实现：
> 
> 1.  选出坑的位置（基准直）；![ead910d872ee4f92b96aab6d6ae4d36d.png][]
> 2.  第一次排序；![f21e3f1489c745e8b1cc980a11dcbadf.png][]
> 3.  递归排序左、右子序列。![90bc79f6f3664850b9f1c4eefb3be30b.png][]

#### 2、2、3 挖坑法代码实现 ####

void Swap(int* p1, int* p2)
    {
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    void QuickSort(int arr[], int left, int right)
    {
    	if (left >= right)
    	{
    		return;
    	}
    	int index = GetMid(arr, left, right);
    	Swap(&arr[left], &arr[index]);
    	int begin = left;
    	int end = right;
    	int pivot = begin;
    	int key = arr[begin];
    	while (begin < end)
    	{
    		while (begin<end && arr[end] >= key)
    		{
    			end--;
    		}
    		arr[pivot] = arr[end];
    		pivot = end;
    		while (begin < end && arr[begin] <= key)
    		{
    			begin++;
    		}
    		arr[pivot] = arr[begin];
    		pivot = begin;
    	}
    	arr[begin] = key;
    	QuickSort(arr, left, begin - 1);
    	QuickSort(arr, begin + 1, right);
    }
    void Print(int arr[], int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    }
    void TestSort()
    {
    	int arr[10] = { 0,9,8,7,6,5,4,3,2,1 };
    	int n = 10;
    	QuickSort(arr, 0, n - 1);
    	Print(arr, n);
    }
    int main()
    {
    	TestSort();
    	return 0;
    }

### 2、3 左右指针法 ###

#### 2、3、1 左右指针法实现思想 ####

> 我们先来了解一下**左右指针法的主要思想：**
> 
> 1.  先选出一个基准值，我们选择坑的位置一般会选最左边或者最右边或者中间的数据。
> 2.  第一次排序：**我们定义两个指针。**初始时，一个指针**（begin指针）**指向最左边的数据，另一个指针**（end指针）**指向最后一个数据。begin指针向右找比基准值大的数据，找到了就停下来。end指针向左找比基准值小的数据，找到了就停下来。然后交换两个指针的指向的数据，**直到begin指针与end指针相遇，最后把基准值与begin与end相遇位置的数据交换即可。**
> 3.  递归左右子区重复第二步骤的操作达到有序。

#### 2、3、2 左右指针法举例 ####

> 同样，我们先给出一个数组，如下：

![0ffa11dc8c074876843abbb813a6db79.png][]

> 我们用上述的左右指针法的思想来实现一下：
> 
> 1.  选出一个基准直（数组最左边的值）；
> 2.  定义左右指针，依次往中间找；![41e0a64b2cac4f9fa939bedaf04659e3.png][]
> 3.  递归左右子区间重复第二步骤达到有序。

#### 2、3、3 左右指针法代码实现 ####

#include<stdio.h>
    void Print(int arr[], int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    }
    void Swap(int* p1, int* p2)
    {
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    void QuickSort(int arr[], int left, int right)
    {
    	if (left >= right)
    		return;
    	int begin = left;
    	int end = right;
    	int keyi = begin;
    	while (begin < end)
    	{
    		while (begin < end && arr[end] >= arr[keyi])
    		{
    			end--;
    		}
    		while (begin < end && arr[begin] <= arr[keyi])
    		{
    			begin++;
    		}
    		Swap(&arr[begin], &arr[end]);
    	}
    	Swap(&arr[begin], &arr[keyi]);
    	QuickSort(arr, left, begin - 1);
    	QuickSort(arr, begin + 1, right);
    }
    void TestSort()
    {
    	int arr[] = { 3,5,1,2,7,6,4,5,8,0,9,-1 };
    	int n = 12;
    	QuickSort(arr, 0, n - 1);
    	Print(arr,n);
    }
    int main()
    {
    	TestSort();
    	return 0;
    }

### 2、4 前后指针法 ###

#### 2、4、1 前后指针发实现思想 ####

> 我们先来了解一下**前后指针法的主要思想：**
> 
> 1.  先选出一个基准值，我们一般只会选择第一个数据作为基准值；
> 2.  第一次排序：我们**定义两个指针（前后指针）**。初始时，前指针（prev指针）指向最左边的数据，后指针（cur指针）指向第二个数据。cur指针向右找比基准值小的数据，找到了就停下来。然后perv指针加一，cur指针与prev指针指向的数据交换。直到cur指针找到最右边停止。**最后再把基准值与prev数据交换一下即可。**
> 3.  递归左右子区重复第二步骤的操作达到有序。

#### 2、4、2 前后指针法举例 ####

> 老样子，我们先给出一个数组，如下：

![0ffa11dc8c074876843abbb813a6db79.png][]

> 我们用上述的前后指针法的思想来实现一下：
> 
> 1.  先选出一个基准值；
> 2.  定义前后指针，进行第一次排序；![4fc16f10b72d499bb4ab9658860ac261.png][]
> 3.  递归实现左右子序列。

#### 2、4、3 前后指针代码实现 ####

#include<stdio.h>
    void Print(int arr[], int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    }
    void Swap(int* p1, int* p2)
    {
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    void QuickSort(int arr[], int left, int right)
    {
    	int keyi = left;
    	int prev = left;
    	int cur = left + 1;
    	while (cur <= right)
    	{
    		while (arr[cur] < arr[keyi] && ++prev != cur)
    		{
    			Swap(&arr[cur], &arr[prev]);
    		}
    		cur++;
    	}
    	Swap(&arr[keyi], &arr[prev]);
    	QuickSort(arr, left, prev - 1);
    	QuickSort(arr, prev + 1, right);
    }
    void TestSort()
    {
    	int arr[] = { 3,5,1,2,7,6,4,5,8,0,9,-1 };
    	int n = 12;
    	QuickSort(arr, 0, n - 1);
    	Print(arr,n);
    }
    int main()
    {
    	TestSort();
    	return 0;
    }

> 以上就是快速排序的三种不同的实现方法，但是实现的基本思想是大同小异的。接下来我们看一下归并排序。

## 三、归并排序的思想及代码详解 ##

> 归并排序的思想与快速排序的思想有一点相似之处，但又有些不同。当我们理解了快速排序后，归并排序理解起来也就是跟简单了。我们来看一下归并排序的思想实现。

### 3、1 归并排序的思想实现 ###

> 归并排序（MERGE-SORT）是建立在**归并操作**上的一种有效的排序算法,该算法是**采用分治法（Divide and Conquer）**的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
> 
> 我们同样将归并排序分为**三大步骤：**
> 
> 1.  找出数组个数的中间值，将数组非为左右子区间；
> 2.  **递归找到最小的左右区间**；
> 3.  依次将**最小的左右（有序）**区间进行归并操作得到有序数组。
> 
> 我们结合下面的举例图片更容易理解。

![a0b1ea182e0848839d5b70f329a6b8f6.png][]

### 3、2 归并排序的代码实现 ###

void MergeSort(int arr[], int left, int right,int tmp[])
    {
    	if (left >= right)
    		return;
    	int mid = left + right >> 1;
    	MergeSort(arr, left, mid, tmp);
    	MergeSort(arr, mid + 1, right, tmp);
    
    	int begin1 = left;
    	int end1 = mid;
    	int begin2 = mid + 1;
    	int end2 = right;
    	int index = left;
    	while (begin1 <= end1 && begin2 <= end2)
    	{
    		if (arr[begin1] < arr[begin2])
    			tmp[index++] = arr[begin1++];
    		else
    			tmp[index++] = arr[begin2++];
    	}
    	while (begin1 <= end1)
    	{
    		tmp[index++] = arr[begin1++];
    	}
    	while (begin2 <= end2)
    	{
    		tmp[index++] = arr[begin2++];
    	}
    	for (int i = left; i <= right; i++)
    	{
    		arr[i] = tmp[i];
    	}
    }
    void TestSort()
    {
    	int arr[] = { 3,5,1,2,7,6,4,5,8,0,9,-1 };
    	int n = 12;
    	int tmp[12];
    	QuickSort(arr, 0, n - 1，tmp);
    	Print(arr,n);
    }
    int main()
    {
    	TestSort();
    	return 0;
    }

## 总结 ##

> 通过上面的学习，我们发现快速排序和归并排序都用了分治的思想来实现的。**分支的思想就是把一个复杂的问题分解成很多相对较容易的问题，通过实现相对较容易的小问题后，一步一步返回完成复杂的大问题。** 分支的思想在快速排序和归并排序中就得到了很好的体现。快速排序和归并排序在排序中相对来说是十分重要的，我们应该反复练习，达到熟能生巧的地步。

> 快速排序和归并排序就讲到这里，希望本篇文章对你有所帮助，后续会持续更新**堆排序**的详解。
> 
> 感谢阅读ovo~

[76c5a476909240ce9c8ec5c8b0c115e6.png]: https://img-blog.csdnimg.cn/76c5a476909240ce9c8ec5c8b0c115e6.png
[48ab921c6ccc46a0b7954b68b0e874b8.png]: https://img-blog.csdnimg.cn/48ab921c6ccc46a0b7954b68b0e874b8.png
[cb6eb295ff964cf4ae69a45b5ba770ea.png]: https://img-blog.csdnimg.cn/cb6eb295ff964cf4ae69a45b5ba770ea.png
[3e677920a92d4465a6e44cbc6916c455.png]: https://img-blog.csdnimg.cn/3e677920a92d4465a6e44cbc6916c455.png
[a329dd95da894bbb8bf1b9802a28b9f6.png]: https://img-blog.csdnimg.cn/a329dd95da894bbb8bf1b9802a28b9f6.png
[ead910d872ee4f92b96aab6d6ae4d36d.png]: https://img-blog.csdnimg.cn/ead910d872ee4f92b96aab6d6ae4d36d.png
[f21e3f1489c745e8b1cc980a11dcbadf.png]: https://img-blog.csdnimg.cn/f21e3f1489c745e8b1cc980a11dcbadf.png
[90bc79f6f3664850b9f1c4eefb3be30b.png]: https://img-blog.csdnimg.cn/90bc79f6f3664850b9f1c4eefb3be30b.png
[0ffa11dc8c074876843abbb813a6db79.png]: https://img-blog.csdnimg.cn/0ffa11dc8c074876843abbb813a6db79.png
[41e0a64b2cac4f9fa939bedaf04659e3.png]: https://img-blog.csdnimg.cn/41e0a64b2cac4f9fa939bedaf04659e3.png
[4fc16f10b72d499bb4ab9658860ac261.png]: https://img-blog.csdnimg.cn/4fc16f10b72d499bb4ab9658860ac261.png
[a0b1ea182e0848839d5b70f329a6b8f6.png]: https://img-blog.csdnimg.cn/a0b1ea182e0848839d5b70f329a6b8f6.png