快速排序

## 快速排序
![](/media/202205/QuickSort_1653713904.gif)

**基本思想：**
- 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

**算法描述：**
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
1. 从数列中挑出一个元素，称为 “基准”（pivot ）
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

### Hoare版本(递归)
![](/media/202205/QuickSort_Hoare_1653714110.gif)
Hoare版本的单趟排序的基本步骤如下：
1. 选出一个key，一般是最左边或是最右边的
2. 定义一个L和一个R，L从左向右走，R从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要R先走；若选择最右边的数据作为key，则需要L先走）
3. 在走的过程中，若R遇到小于key的数，则停下，L开始走，直到L遇到一个大于key的数时，将L和R的内容交换，R再次开始走，如此进行下去，直到L和R最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key
然后我们在将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，因为这种序列可以认为是有序的

[wokwi_Hoare版本](https://wokwi.com/projects/332887501865747027)|[wokwi_Hoare版本](https://wokwi.com/projects/334327145560015442)
```c
// 快速排序(Hoare版本),QuickSortHoare(数组名,数组长度,[排序方向,默认小到大])
void QuickSortHoare(int array[], int size, boolean forward = true){
	// 因为数组是从0开始,所以结束下标为 数组长度-1
	_QuickSortHoare(array, 0, size-1);
	if(!forward){
		// 暂存数组,空间和排序数组一致
		int temp[size];
		// 把排序数组整个逆向存入暂存数组
		// size-1-i,数组长度(10)-1为最后位下标,-i就是从后往先递进
		for (int i = 0; i < size; i++) temp[i] = array[size-1-i];
		// 暂存数组复制到排序数组以完成逆向排序
		for (int i = 0; i < size; i++) array[i] = temp[i];
	}
}
//快速排序(Hoare版本),_QuickSortHoare(数组名,开始下标,结束下标,排序方向),递归主体
void _QuickSortHoare(int* array, int begin, int end){
	// 当只有一个数据(标记指向同元素)或是序列不存在时,不需要进行操作,直接跳出
	if (begin >= end) return;
	int left = begin; // L
	int right = end;  // R
	int key = left; // key的下标
	// 判断两个标记位置是否重合,重合意味该趟排序完成
	while (left < right){
		//right先走，找小
		while (left < right && array[right] >= array[key]) right--;
		//left后走，找大
		while (left < right && array[left] <= array[key]) left++;
		//交换left和right的值
		if (left < right) swap(array[left], array[right]);
	}
	int meeti = left; // 两个标记位的相遇点
	swap(array[key], array[meeti]); // 交换key和相遇点的值

_QuickSortHoare(array, begin, meeti - 1); // key的左序列进行递归
	_QuickSortHoare(array, meeti + 1, end); // key的右序列进行递归
}
// 元素换位函数,因为频繁使用,就单独定义函数了
void swap(int &a,int &b){
	int c=a;
	a=b;
	b=c;
}
```

### 挖坑法(递归)
![](/media/202205/QuickSort_挖坑法_1653723762.gif)

挖坑法的基本步骤如下:
1. 定义两个标记(sign1,sign2)，sign2 也就是 key，等待填入的
2. 移动比较，根据方向不同有两种情况：
	sign1➡️ ⬅️sign2
		在走的过程中，若 sign1 < sign2 ，则将 sign1 和 sign2 的内容交换，并且把 sign1 和 sign2 也交换(sign2➡️ ⬅️sign1)，然后 sign1 向 sign2 移动一步，指向下一组元素
	sign2➡️ ⬅️sign1
		在走的过程中，若 sign2 > sign1 ，则将 sign1 和 sign2 的内容交换，并且把 sign1 和 sign2 也交换(sign1➡️ ⬅️sign2)，然后 sign1 向 sign2 移动一步，指向下一组元素
3. 直到 sign1 和 sign2 位置重合，这趟排序就算结束
4. 经过一次单趟排序，最终使得 sign1 停留位置左边的数据全部都小于 sign1，右边的数据全部都大于 sign1
5. 然后我们在将 sign1 的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，因为这种序列可以认为是有序的

[wokwi_快速排序(挖坑法)](https://wokwi.com/projects/332884180996194898)|[wokwi_快速排序(挖坑法)](https://wokwi.com/projects/334327181168607827)
```c
// 快速排序(挖坑法),QuickSortHoare(数组名,数组长度,[排序方向,默认小到大])
void QuickSortHoare(int array[], int size,boolean forward = true){
	// 因为数组是从0开始,所以结束下标为 数组长度-1
	_QuickSortHoare(array, 0, size-1, forward);
}
// 快速排序(挖坑法)_QuickSortHoare(数组名,开始下标,结束下标,排序方向),递归主体
void _QuickSortHoare(int* array, int begin, int end, boolean forward){
	// 当只有一个数据(标记指向同元素)或是序列不存在时,不需要进行操作,直接跳出
	if(begin>=end) return;
	// 初始化两个标记位置
	int sign1=begin;
	int sign2=end;
	// 判断两个标记位置是否重合,重合意味该趟排序完成
	while(sign1!=sign2){
		// 根据两个标记指定下标区分方向
		// sign1<sign2 意味着 sign1在左侧,sign2在右侧
		if(sign1<sign2){
			// 定义存储比较结果的变量
			boolean compare;
			// 根据传入的第三个参数,来确定是正向排序(小到大)还是逆向排序(大到小)
			if (forward == true) compare = array[sign1]>array[sign2];
			else compare = array[sign1]<array[sign2];
			// 那么当遇到 sign1>sign2,则需要把两个元素换位
			if(compare){
				// 元素换位
				swap(array[sign2],array[sign1]);
				// 两个下标也要换位,这样可以尽可能的把数组拆分成两等份
				swap(sign2,sign1);
				// 换位后把 sign1 左移一位(这时候sign1在右侧)开始下一轮比较
				sign1--;
			}else sign1++;    // 不成立则sign1继续右移(sign1在左侧)进行新比较
		}else if(sign1>sign2){
			// 定义存储比较结果的变量
			boolean compare;
			if (forward == true) compare = array[sign1]<array[sign2];
			else compare = array[sign1]>array[sign2];
			// 同理,不过是方向为反向的,sign1在右,sign2在左
			if(compare){
				swap(array[sign2],array[sign1]);
				swap(sign2,sign1);
				sign1++;
			}else sign1--;
		}
	}
	// 递归,把最后sign1停留的位置作为中线,左侧和右侧各自递归完成排序
	// sign1所在位置的数值因为之前已经确定好位置了,所以并不参与后面的递归
	// 一直递归直到当只有一个数据(标记指向同元素)或是序列不存在时结束,这时候数组就完成了排序
	_QuickSortHoare(array, begin, sign1 - 1); // key的左序列进行递归
	_QuickSortHoare(array, sign1 + 1, end); // key的右序列进行递归
}
// 元素换位函数,因为频繁使用,就单独定义函数了
void swap(int &a,int &b){
	int c=a;
	a=b;
	b=c;
}
```

## 其他方式
快速排序还有很多实现方式，递归的也可借助于栈来改造成无需递归的
更加详细的方式查看 [八大排序算法(C语言实现)——快速排序](https://blog.csdn.net/chenlong_cxy/article/details/116563972#_299)