【数据结构】排序（二）——快速排序（细节版）

码农世界 2024-05-27 后端 66 次浏览 0个评论

书接上回：【数据结构】排序（一）—— 希尔排序（思路演进版）-CSDN博客

二、常见排序算法的实现

2.2选择排序

2.2.1直接选择排序

思路

❓实现细节

完整代码

测试结果

2.2.2堆排序

思路

❓实现细节

完整代码

测试结果

2.3交换排序

2.3.1冒泡排序

思路

代码实现

测试结果

2.3.2快速排序

2.3.2.1递归实现

总体思路

1.hoare版本

思路描述

❓总结实现细节

递归部分

修改代码

测试结果

优化：三数取中

优化后完整代码

2.挖坑法

思路描述

代码实现

完整代码

3.前后指针法

思路归纳

代码实现

完整代码

2.3.2.2非递归实现

大致思路

❓细节

代码实现

测试结果

总结

Tips

二、常见排序算法的实现

2.2选择排序

2.2.1直接选择排序

思路

内层

遍历所有元素,[begin , end]之间选出最大的元素和最小的元素的下标。

最大的元素放后面，最小的元素放前面。

begin++ end--

外层

[begin,end]区间逐渐缩小，直到begin、end两个下标相遇为止。

❓实现细节

把最小值放最左边没有问题，但是最左边位置begin 有可能跟最大值maxi的位置重叠，为了防止重叠，加一个判断。如果重叠了，把最大值的新下表还给maxi.新下标此时就是mini.

完整代码

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void SelectSort(int* a, int n)
{
	int begin = 0, end = n-1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[mini], &a[begin]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}

测试结果

2.2.2堆排序

思路

1.向下调整建堆从第一个非孩子节点开始向下调整建堆，第一个非孩子节点也就是最后一个孩子的父结点

2.堆顶元素和尾元素交换

3.然后把新的堆顶元素向下调整

❓实现细节

完整代码

// 堆排序 建大堆 排升序
void AdjustDwon(int* a, int n, int root)
{
	int child = root * 2 + 1;
	while (child < n)
	{
		//假设法：假设左孩子 是较大的孩子 如果左不是较大 则更新为有右孩子
		if (child+1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		//建大堆 如果父节点 小于 孩子节点 则交换
		if (a[root] < a[child])
		{
			Swap(&a[root], &a[child]);
			//更新父节点 孩子节点
			root = child;
			child = root * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//向下调整建堆 从第一个非孩子节点开始向下调整建堆 ， 第一个非孩子节点也就是最后一个孩子的父结点
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//堆顶元素 和 尾元素 交换
		Swap(&a[0], &a[end]);
		//然后把新的堆顶元素向下调整
		AdjustDwon(a, end, 0);
		end--;
	}
}

测试结果

2.3交换排序

2.3.1冒泡排序

思路

单趟控制

若i从1开始则i
若i从0开始则i
总体控制

控制每次单趟走的范围

代码实现

// 冒泡排序
//单趟 ： i与i+1比较
void BubbleSort(int* a, int n)
{
	//控制每次 单趟 走的范围
	for (int j = 0; j < n - 1; j++)
	{
		//单趟
		for (int i = 0; i < n - 1 - j; i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
	}
}

测试结果

2.3.2快速排序

2.3.2.1递归实现

总体思路

先用左右下标遍历一次数组，确定key应该所在位置的下标keyi，把数组分为左边，右边。

继续递归调用函数使左边有序，右边有序，则整体有序。

下面三个版本在总体思路上没有区别，区别在于第一次遍历数组时，如何找到key正确所在位置的下标keyi。我们将有区别的过程分别封装成三个版本的PartSort()函数。对于实现不同版本的PartSort()函数的思路，进行逐一讲解：

1.hoare版本

思路描述

在数组里选择最左边的值做key，并且记录数组左端右端两个下标（left、right）。
right负责找小，如果right比key大，right--继续往前找，right停止即找到比key小的数
left负责找大，如果left比key小 ,left++继续往后走，left停止即找到比key大的数
然后交换left,right两个下标的数
重复上述步骤，直到left和right相遇 left 、right停止，相遇即停。
最后key和left交换，结果呈现是 key之前都比key小，key之后都比key大。

注意：

key取左值，则需要right先走去找小！

才能保证key和left交换是把小的换到前面，大的值换到后面。（后面讲解）

key取右值，则需要left先走去找大！

左边做key R先走

右边做key L先走

（初级版本）我们对上述思路尝试实现：

经过调试，我们发现left找大的循环并没有进入所以left 要给成begin+1

❓总结实现细节

❓细节1：Left 从 begin or begin+1 开始？

答：从begin+1开始

❓细节2：相遇即停如何控制？

答：虽然外层判断left
当left、right 错位了再找比key大或小的值就没有意义了！！！

所以给负责找大找小的循环要加上left
这样就控制了相遇即停

❓细节3：右边先走可以保证相遇位置比 key小？为什么？

答：相遇有两种情况：

①R遇L——>R没有找到比K小的数一直走直到遇到L 相遇位置是L 比key小

②L遇R——>R 先走找到小的停下来了 L找大没有找到，遇到R停下来了，相遇位置是R,(比key小)

❓细节4 —— k：keyi取 0 or left？

答：keyi给0

❓细节5：相遇后 a[left] 和谁交换？

答：key = a[0] 记录下标对应的值, keyi=0 记录位置的下标,

所以是和keyi所记录位置的下标里的值进行交换

❓细节6：进一步考虑更多的应用场景：

如果左边有和 key 相等的值右边也有和key 相等的值，会发生什么情况？

左边找大把循环条件写为 a[left]找到跟Key 相等的数也会停下来左边跟key相等的数与右边跟key 相等的数会交换重复上面的过程进入死循环

所以条件应该写为 a[left]<=a[keyi] a[right]>=a[left]！！！

PartSort1()实现

接下来整体考虑如何实现

递归部分

终止条件：需要排序的区间只剩一个元素或者不存在元素

Begin == end 区间只剩一个元素、 Begin>end 区间不存在值就返回

当递归重复调用PartSort1()函数，结果并不对，经过调试，圈红的两处被发现存在问题

❓细节： Left=begin+1 or left = begin？

假如其中一次递归调用传进去的区间内元素恰好有序，left=begin+1 a[left]跟a[keyi]交换，会使本来有序的被换成无序的。left = begin正确。

❓细节：递归循环调用,会传入不同的区间，所以起始点不是每次都是数组首元素a[0] ，所以keyi 不能写死。

修改代码

// 快速排序hoare版本
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		//right找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//left找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	//left和right相遇,key和left交换
	Swap(&a[left], &a[keyi]);
	keyi = left;
	return keyi;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

测试结果

优化：三数取中

三数取中：下标是 begin end midi 的三个元素中选出一个中位数。

由于在有序的情况下，快速排序更加吃亏。

原因：

①如果每次选key最接近二分查找效率最高时间复杂度 O(N*logN)

单趟是两层循环套在一起但时间复杂度是O(N) 因为是有左右两个下标套在一起遍历完整个数组左边下标走一部分右边下标走一部分。

总共要走多上 logN 趟，所以最好情况时间复杂度是O(N*logN)

②如果是有序的情况，每次的key都固定在最左边的情况，那么时间复杂度为O(N^2)

解决方案：

三数取中避免key 选到最小的或者最大的, 同时解决了整个数据是有序的话不用三数取中的方法对key进行筛选快排的递归层数过深编译器在Debug版本下会导致栈溢出！！！

知识小拓展：

Realse 为什么不会栈溢出？因为Realse版本下会中间优化一些步骤

Debug 版本是要用来调试，调试的本质是往编译文件里打入很多调试信息，本质也是在启动另外一个进程。另外一个进程对当前在正在执行的进程进行追溯，方便程序员看各种信息。

优化后完整代码

//hoare版本 完整代码：
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] > a[end])
	{
		if (a[end] > a[midi])
			return end;
		else if (a[midi] > a[begin])
			return begin;
		else
			return midi;
	}
	else //a[end]>a[begin]
	{
		if (a[midi] > a[end])
			return end;
		else if (a[begin] > a[midi])
			return begin;
		else
			return midi;
	}
}
// 快速排序hoare版本
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end;
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int keyi = begin;
	while (left < right)
	{
		//right找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//left找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	//left和right相遇,key和left交换
	Swap(&a[left], &a[keyi]);
	keyi = left;
	return keyi;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

2.挖坑法

思路描述

先把key从数组中取出来（先用key把左值存起来）形成一个坑位，右下标先开始找小，找到比key小的数放到坑位，右下标此时就形成了新的坑位。然后左下标开始找大，找到比key大的数，继续放到右下标的坑位......

左下标、右下标相遇时把key放在坑位里。

代码实现

完整代码

// 快速排序挖坑法
int PartSort2(int* a, int begin, int end)
{
	int left = begin, right = end;
	int key = a[begin];
	int hole = begin;
	while (left < right)
	{
		//right找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		//把a[right]放到a[hole] right 位置就是新的坑位
		a[hole] = a[right];
		hole = right;
		//left找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		//把a[left]放到a[hole] left 位置就是新的坑位
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort2(a, begin, end);
	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

3.前后指针法

思路归纳

cur遇到比key大的值，++cur
cur遇到比key小的值，++prev , 交换prev 和 cur 的位置 ++cur
重复上述步骤，直到cur越界

代码实现

完整代码

int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] > a[end])
	{
		if (a[end] > a[midi])
			return end;
		else if (a[midi] > a[begin])
			return begin;
		else
			return midi;
	}
	else //a[end]>a[begin]
	{
		if (a[midi] > a[end])
			return end;
		else if (a[begin] > a[midi])
			return begin;
		else
			return midi;
	}
}
//快速排序前后指针法
int PartSort3(int* a, int begin, int end)
{
	int prev = begin, cur = begin + 1;
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi])
		{
			++prev;
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort3(a, begin, end);
	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

2.3.2.2非递归实现

大致思路

为什么还要掌握非递归：因为非递归建立在对递归理解的基础之上，掌握非递归会对递归理解更深刻。

思考递归如何改成非递归？

循环
借助栈

由于双目递归是无法使用循环改的，所以我们借助数据结构的栈。

❓细节

注意栈是先进后出所以我们先入 end 后入 begin 之后出的时候就是，先出begin 后出end。

当栈不为空，Begin end 出来，走一个单趟排序

排完单趟有两个区间 [left,keyi-1] keyi [keyi+1,right] 判断两段区间是否需要入栈

如果区间元素个数还大于一则该区间还需要排序那么入栈（先右后左）

代码实现

//Stack.c Stack.h 参考往期博客
//sort.c
//快速排序前后指针法
int PartSort3(int* a, int begin, int end)
{
	int prev = begin, cur = begin + 1;
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi])
		{
			++prev;
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSortNonR(int* a, int begin, int end )
{
	Stack st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort3(a, left, right);//*
		//两个区间 [left,keyi-1] keyi [keyi+1,right] 
		//判断两段区间 是否需要入栈
		//如果 区间元素个数还大于一 则该区间还需要排序 那么入栈（先右后左）
		if (left < keyi-1)
		{
			StackPush(&st,keyi - 1);
			StackPush(&st, left);
		}
		if (right > keyi + 1)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
	}
}
//test.c
TestQuickSortNonR()
{
	int a[] = { 6,1,2,6,7,9,3,4,5,6,10,8 };
	int b[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
	QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);
	QuickSortNonR(b, 0, sizeof(b) / sizeof(int) - 1);
	PrintArr(a, sizeof(a) / sizeof(int));
	printf("\n");
	PrintArr(b, sizeof(b) / sizeof(int));
}
int main()
{
	TestQuickSortNonR();
	return 0;
}

测试结果

总结

使用递归方法的本质是把记录区间的两个下标（也就是区间）存在函数栈帧里。

利用栈的性质先入后出比如先入右后入左的情况就要把第一趟排完分割好的左区间全部处理完才能处理压在栈底的右区间直到栈为空说明所有区间都已经排好，那么整体结果就有序了。

处理左区间的过程中，出大区间入小的被分割的区间直到被分割出的区间没有值或者只有一个值则不入栈的操作模拟了递归的终止条件！！！

非递归的方法不是递归但胜似递归，实际是对递归方法，利用数据结构的栈（在堆开辟的空间）模拟了函数在栈帧（在栈上开辟空间）上的操作

Tips

数据结构中的堆、栈是一种数据结构

操作系统中的堆、栈是对内存区域的划分一块内存空间的名称

“在栈上开辟空间、在堆开辟的空间”说的是内存空间的名称，

本接内容到此结束，感谢阅读！

下一节，我们将重点讲述归并排序的递归以及非递归版本~

转载请注明来自码农世界，本文标题：《【数据结构】排序（二）——快速排序（细节版）》

码农世界 37815篇文章站点微博

每一天，每一秒，你所做的决定都会改变你的人生！

发表评论取消回复

评论列表（暂无评论，66人围观）参与讨论

码农世界管理员

【数据结构】排序（二）——快速排序（细节版）

二、常见排序算法的实现

2.2选择排序

2.2.1直接选择排序

思路

❓实现细节

完整代码

测试结果

2.2.2堆排序

思路

❓实现细节

完整代码

测试结果

2.3交换排序

2.3.1冒泡排序

思路

代码实现

测试结果

2.3.2快速排序

2.3.2.1递归实现

总体思路

1.hoare版本

思路描述

❓总结实现细节

递归部分

修改代码

测试结果

优化：三数取中

优化后完整代码

2.挖坑法

思路描述

代码实现

完整代码

3.前后指针法

思路归纳

代码实现

完整代码

2.3.2.2非递归实现

大致思路

❓细节

代码实现

测试结果

总结

Tips

Visual Studio 连接 MySQL 数据库 实现数据库的读写（C++）

[工业自动化-1]：PLC架构与工作原理

网络编程（六）TCP并发服务器

Vue3、Element Plus使用v-for循环el-form表单进行校验

Ceph: vdbench 测试ceph存储rbd块设备

linux如何部署前端项目和安装nginx

Windows OpenVPN的安装之服务器自动启动连接

服务器数据恢复—KVM虚拟机被误删除如何恢复虚拟磁盘文件？

发表评论取消回复

还没有评论，来说两句吧...

文章目录

Visual Studio 连接 MySQL 数据库实现数据库的读写（C++）