【排序算法】—— 快速排序

快速排序的原理是交换排序，其中qsort函数用的排序原理就是快速排序，它是一种效率较高的不稳定函数，时间复杂度为O(N*longN)，接下来就来学习一下快速排序。

一、快速排序思路

1.整体思路

以升序排序为例：

(1)、首先随便找一个数(一般取首元素)作为排序对象(记为key)，先将这个数排到准确的位置，即把小于等于key的全部放在key左边，大于key的全部放在key右边。这是排一趟需要做的事。

(2)、排完一趟后被排的那个数key此时它在的位置是准确的，接下来只需要用同样的方法分别对它的左数组和右数组排序，这就有点类似于二叉树的前序遍历。

如下：

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)//如果左区间>=右区间就不用再排，直接返回。
		return;
	int key=_Sort3(arr, left, right);//该函数用来排单趟
	QuickSort(arr, left, key - 1);
	QuickSort(arr, key + 1, right);
}

至于排单趟的算法一般有三种分别是：霍尔法，挖坑法，前后指针法。在下面会细讲。

2.单趟排序

2.1.霍尔法

把第一个元素当排序对象key(首元素的下标)，用L储存左下标，R储存右下标。先让R从右往左走找到比key小的元素时停下，然后让L从左往右走找到比key大的元素停下。然后把位于L位置和位于R位置的的值进行交换，最后重复上面的操作直到L>=R为止。再把key的位置与L位置的值交换。至此一趟排序就结束了。

代码示例：

int _Sort1(int* arr, int begin, int end)//霍尔法
{
	int key = begin;
	while (begin < end)
	{
		while (begin < end && arr[end] > arr[key])
			end--;
		while (begin < end && arr[begin] <= arr[key])
			begin++;
		Swap(&arr[begin], &arr[end]);
	}
	Swap(&arr[key], &arr[begin]);
	key = begin;
	return key;
}

2.1.挖坑法

把首元素当做排序对象赋值给key，然后把第一个下标L当做坑位，让R从右边出发找到比key小的数放在坑位，然后R的位置变成坑位，让L从左往右找到比key大的数放在坑位，L位置变成坑位，再次让R走，循环往复直到L与R相遇。最后把key放在坑位，至此一趟排序结束。

代码示例：

int _Sort2(int* arr, int begin, int end)
{
	int key = arr[begin];
	int kw = begin;//坑位下标
	while (begin < end)
	{
		while (begin < end && arr[begin] < key)
			begin++;
		arr[kw] = arr[begin];
		kw = begin;
		while (begin < end && arr[end] >= key)
			end--;
		arr[kw] = arr[end];
		kw = end;
	}
	arr[kw] = key;
	return kw;
}

2.3.前后指针法

把第一个元素当排序对象key(首元素的下标)，prev指向首元素下标，cur指向首元素下一个元素下标。

如果cur指向的元素小于key的话prev向右走，并且如果prev不等于cur，那么把prev与cur互换。最后cur都需要无条件向右走一步。

代码示例：

int _Sort3(int* arr, int begin, int end)//前后指针法
{
	int perv = begin, cur = begin + 1;
	while (cur <= end)
	{
		if (arr[cur] < arr[begin] && ++perv != cur)
			Swap(&arr[perv], &arr[cur]);
		cur++;
	}
	Swap(&arr[perv], &arr[begin]);
	return perv;
}

二、提供效率的方法

1.三数取中(key值的选取)

快速排序的"三数取中"（Median of Three）是一种优化技术，它相当于选排序对象key。其具体做法如下：

        (1).选择三个元素：从待排序数组中选择三个关键元素，通常是第一个元素、中间元素和最后一个元素。
        (2).比较并选择中位数：将这三个元素进行比较，选择值不是最大也不是最小的数。比如，如果三个元素分别是arr[left]、arr[mid]、arr[right]，则中位数是介于这三个值之间的那个数。
        (3).交换为第一个元素：将选定的中位数元素与数组的第一个元素交换位置，以便在后续的快速排序中使用。

通过使用"三数取中"的方法，可以有效地减少快速排序中最坏情况的发生概率，因为选取的主元更有可能接近数组的中值，而不是极端值。这样可以更均匀地划分数组，减少排序的平均时间复杂度，提高算法的整体性能。

2.小区间优化

小区间优化指的是在快速排序算法中针对较小规模的子数组（或子问题）采用其他排序方法，而不是继续使用快速排序本身。这种优化技术的目的是避免在小规模问题上快速排序的递归调用带来的额外开销，提高算法的整体效率。
具体来说，当快速排序的递归过程划分的子数组规模减小到一定程度时，可以选择使用插入排序或其他适合小规模数组的排序方法来处理。这样可以避免递归深度过深，减少递归调用和分区操作的开销，从而提高整体排序算法的性能。
具体的优化策略包括：

(1).设定阈值：在实现快速排序时设定一个阈值，当子数组的大小小于这个阈值时，转而使用插入排序或者直接选择排序等方法进行排序。常见的阈值一般设定在5到10之间，具体取决于具体实现和排序数据的特性。
(2).切换到其他排序算法：在快速排序的递归过程中，当子数组大小小于设定的阈值时，停止快速排序的递归，转而使用其他排序算法完成剩余的排序工作。

小区间优化技术能有效降低快速排序在小规模数据上的不必要开销，提高整体排序算法的效率和性能。

三、非递归实现

把递归该为非递归毋庸置疑首先考虑使用栈结构，这里我们需要抓住重点，考虑需要用栈结构储存什么数据，先从函数参数上看左右区间的参数是一直在变化的，那么只需要把区间储存到栈中，每次从栈中就可以取到需要排序的区间，对这个区间进行一趟排序后再分为两个小区间存入栈中，重复以上操作直到栈为空。

四、源码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"Stack.h"
#define size 100
void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
void InsertSort(int* arr, int sz)//插入排序(小区间优化)
{
	for (int i = 0; i < sz - 1; i++)
	{
		int j = i;
		int tmp = arr[j + 1];
		while (j >= 0 && tmp < arr[j])
		{
			arr[j + 1] = arr[j--];
		}
		arr[j + 1] = tmp;
	}
}
int Sk(int* arr, int left, int right)//三数取中
{
	int v = (left + right) / 2;
	if (arr[left] > arr[right])
	{
		if (arr[right] > arr[v])
			return right;
		else
		{
			if (arr[left] < arr[v])
				return left;
			else
				return v;
		}
	}
	else
	{
		if (arr[left] > arr[v])
			return left;
		else
		{
			if (arr[right] > arr[v])
				return right;
			else
				return v;
		}
	}
}
int _Sort1(int* arr, int begin, int end)//霍尔法
{
	int key = begin;
	while (begin < end)
	{
		while (begin < end && arr[end] > arr[key])
			end--;
		while (begin < end && arr[begin] <= arr[key])
			begin++;
		Swap(&arr[begin], &arr[end]);
	}
	Swap(&arr[key], &arr[begin]);
	key = begin;
	return key;
}
int _Sort2(int* arr, int begin, int end)//挖坑法
{
	int val = arr[begin];
	int kw = begin;//坑位
	while (begin < end)
	{
		while (begin < end && arr[begin] < val)
			begin++;
		arr[kw] = arr[begin];
		kw = begin;
		while (begin < end && arr[end] >= val)
			end--;
		arr[kw] = arr[end];
		kw = end;
	}
	arr[kw] = val;
	return kw;
}
int _Sort3(int* arr, int begin, int end)//前后指针法
{
	int perv = begin, cur = begin + 1;
	while (cur <= end)
	{
		if (arr[cur] < arr[begin] && ++perv != cur)
			Swap(&arr[perv], &arr[cur]);
		cur++;
	}
	Swap(&arr[perv], &arr[begin]);
	return perv;
}
void QuickSort(int* arr, int left, int right)//快速排序(递归实现)
{
	if (left >= right)
		return;
	if (right - left <= 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}
	int key=_Sort1(arr, left, right);
	QuickSort(arr, left, key - 1);
	QuickSort(arr, key + 1, right);
}
void QuickSortNoR(int* arr, int left, int right)//快速排序(非递归)
{
	Stack st;
	StackInit(&st);//关于栈结构的函数实现在这里并未展示，已在Stack.h中声明
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int perv = begin, cur = begin + 1;
		int end = StackTop(&st);
		StackPop(&st);
		if (begin >= end)
			continue;
		while (cur <= end)
		{
			if (arr[cur] < arr[begin] && ++perv != cur)
				Swap(&arr[cur], &arr[perv]);
			cur++;
		}
		Swap(&arr[begin], &arr[perv]);
		StackPush(&st, end), StackPush(&st, perv + 1);
		StackPush(&st, perv - 1), StackPush(&st, begin);
	}
	StackDestroy(&st);
}
int main()
{
	int arr[size] = { 0 };
	srand((unsigned int)time(NULL));//随机数种子
	for (int i = 0; i < size; i++)
	{
		arr[i] = rand() % 1000 + 1;//生成随机数赋值给arr[i]
	}
	QuickSort(arr, 0, size - 1);
	for (int i = 0; i < size; i++)
	{
		printf("%-3d ", arr[i]);
		if ((i + 1) % 20 == 0)
			printf("\n");
	}
	return 0;
}