【C语言/数据结构】排序（快速排序及多种优化|递归及非递归版本）

 🌈个人主页：秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏：《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

​​​​

目录

 交换排序

快速排序

 hoare版代码呈现

快排优化

三数取中法

 小区间优化

 挖坑法

 前后指针版本

非递归版本快排

前言

    💬 hello! 各位铁子们大家好哇。

             今日更新了快速排序的内容

    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

 交换排序

快速排序

快排的过程图如下： 

 hoare版代码呈现

void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int left = begin, right =end;
	int keyi = begin;
	while (left = a[keyi])
		{
			right--;
		}
		//左边找大
		while (left 

如果左边做key，R先走。

如果右边做key，L先走。

快排优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序

三数取中法

快排对于有序的数据，效率不是很高。

如上图，我们前面的快排是固定选key的，也就是左边第一幅图，效率很低。理想情况下，每一次都二分，这样效率就能提高。这时就用到三数取中法。

三数取中法指三个数里面取中间大小的数，然后将他与key交换位置，让这个中间大小的数作key。

完整代码如下： 

int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	//begin end midi三个数中选中位数
	if (a[begin]  a[end])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[begin] = end)
		return;
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int left = begin, right = end;
	int keyi = begin;
	while (left = a[keyi])
		{
			right--;
		}
		//左边找大
		while (left  
 
 
 分析：挖坑法其实跟hoare版本比没啥提升，只不过更易理解，本质上没变。但不同的版本，单趟排序后的结果可能会不同。
 
 
 前后指针版本
 
 
 
 
分析：
 
 
cur遇到比key大的值，cur++
cur遇到比key小的值，++prev，交换prev和cur位置的值，++cur
代码实现
 
//前后指针法
int PartSort3(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int keyi = begin;
	int prev = begin;
	int cur = prev + 1;
	while (cur a = NULL;
	pst->capacity = 0;
	pst->top = 0;
	//pst->top = -1;
}
void STDestroy(ST* pst)
{
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
//栈顶插入删除
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return	pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
	assert(pst);
	//if (pst->top == 0)
	//{
	//	return true;
	//}
	//else
	//{
	//	return	false;
	//}
	return pst->top == 0;
}
 
 
 非递归代码实现：
 
void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);
	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);
		int keyi = PartSort3(a, left, right);
		// [left,keyi-1] keyi [keyi+1,right]
		
		if (keyi+1  
 
 
 
分析：栈是后进先出，这里用栈是模拟递归的过程。先模拟递归左边，像二叉树递归那样，先入右边的数，再入左边，这样出的时候就先出左边的，然后就可以模拟先往左边递归了。