devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：AllinToyou | 2024-05-23 23:41:57

赞

踩

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

书接上回：【数据结构】排序（一）—— 希尔排序（思路演进版）-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.

完整代码
  1. void Swap(int* pa, int* pb)
  2. {
  3. 	int tmp = *pa;
  4. 	*pa = *pb;
  5. 	*pb = tmp;
  6. }
  7. void SelectSort(int* a, int n)
  8. {
  9. 	int begin = 0, end = n-1;
  10.  
  11. 	while (begin < end)
  12. 	{
  13. 		int mini = begin, maxi = begin;
  14. 		for (int i = begin + 1; i <= end; ++i)
  15. 		{
  16. 			if (a[i] < a[mini])
  17. 			{
  18. 				mini = i;
  19. 			}
  20. 			if (a[i] > a[maxi])
  21. 			{
  22. 				maxi = i;
  23. 			}
  24. 		}
  25. 		Swap(&a[mini], &a[begin]);
  26. 		if (maxi == begin)
  27. 		{
  28. 			maxi = mini;
  29. 		}
  30. 		Swap(&a[maxi], &a[end]);
  31. 		begin++;
  32. 		end--;
  33. 	}
  34. }
测试结果

2.2.2堆排序

思路

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

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

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

❓实现细节

完整代码
  1. // 堆排序 建大堆 排升序
  2. void AdjustDwon(int* a, int n, int root)
  3. {
  4. 	int child = root * 2 + 1;
  5. 	while (child < n)
  6. 	{
  7. 		//假设法：假设左孩子 是较大的孩子 如果左不是较大 则更新为有右孩子
  8. 		if (child+1 < n && a[child] < a[child + 1])
  9. 		{
  10. 			child++;
  11. 		}
  12. 		//建大堆 如果父节点 小于 孩子节点 则交换
  13. 		if (a[root] < a[child])
  14. 		{
  15. 			Swap(&a[root], &a[child]);
  16. 			//更新父节点 孩子节点
  17. 			root = child;
  18. 			child = root * 2 + 1;
  19. 		}
  20. 		else
  21. 		{
  22. 			break;
  23. 		}
  24. 	}
  25. }
  26. void HeapSort(int* a, int n)
  27. {
  28. 	//向下调整建堆 从第一个非孩子节点开始向下调整建堆 ， 第一个非孩子节点也就是最后一个孩子的父结点
  29. 	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  30. 	{
  31. 		AdjustDwon(a, n, i);
  32. 	}
  33. 	int end = n - 1;
  34. 	while (end > 0)
  35. 	{
  36. 		//堆顶元素 和 尾元素 交换
  37. 		Swap(&a[0], &a[end]);
  38. 		//然后把新的堆顶元素向下调整
  39. 		AdjustDwon(a, end, 0);
  40. 		end--;
  41. 	}
  42. }
测试结果

2.3交换排序

2.3.1冒泡排序

思路

单趟控制

若i从1开始 则i<n i-1与i比较

若i从0开始 则i<n i与i+1比较

总体控制

控制每次 单趟 走的范围

代码实现
  1. // 冒泡排序
  2. //单趟 ： i与i+1比较
  3. void BubbleSort(int* a, int n)
  4. {
  5. 	//控制每次 单趟 走的范围
  6. 	for (int j = 0; j < n - 1; j++)
  7. 	{
  8. 		//单趟
  9. 		for (int i = 0; i < n - 1 - j; i++)
  10. 		{
  11. 			if (a[i] > a[i + 1])
  12. 			{
  13. 				Swap(&a[i], &a[i + 1]);
  14. 			}
  15. 		}
  16. 	}
  17. }
测试结果

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<right  但内层循环 left、right 持续在动 不能保证依然满足 left<right 的条件。

当left、right 错位了 再找比key大 或 小 的值 就没有意义了！！！

所以给 负责找大 找小的循环 要加上left<right 的条件！！！

这样就控制了 相遇即停

❓细节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]<a[keyi] 意味着：左边找到比key大的数会停下来 找到跟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 不能写死。

修改代码
  1. // 快速排序hoare版本
  2. int PartSort1(int* a, int begin, int end)
  3. {
  4. 	int left = begin, right = end;
  5. 	int keyi = begin;
  6. 	while (left < right)
  7. 	{
  8. 		//right找小
  9. 		while (left < right && a[right] >= a[keyi])
  10. 		{
  11. 			right--;
  12. 		}
  13. 		//left找大
  14. 		while (left < right && a[left] <= a[keyi])
  15. 		{
  16. 			left++;
  17. 		}
  18. 		Swap(&a[left], &a[right]);
  19. 	}
  20. 	//left和right相遇,key和left交换
  21. 	Swap(&a[left], &a[keyi]);
  22. 	keyi = left;
  23. 	return keyi;
  24. }
  25. void QuickSort(int* a, int begin, int end)
  26. {
  27. 	if (begin >= end)
  28. 	{
  29. 		return;
  30. 	}
  31. 	int keyi = PartSort1(a, begin, end);
  32. 	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
  33. 	QuickSort(a, begin, keyi - 1);
  34. 	QuickSort(a, keyi + 1, end);
  35. }
测试结果

优化：三数取中

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

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

原因：

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

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

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

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

解决方案：

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

知识小拓展：

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

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

优化后完整代码
  1. //hoare版本 完整代码：
  2. int GetMidi(int* a, int begin, int end)
  3. {
  4. 	int midi = (begin + end) / 2;
  5. 	if (a[begin] > a[end])
  6. 	{
  7. 		if (a[end] > a[midi])
  8. 			return end;
  9. 		else if (a[midi] > a[begin])
  10. 			return begin;
  11. 		else
  12. 			return midi;
  13. 	}
  14. 	else //a[end]>a[begin]
  15. 	{
  16. 		if (a[midi] > a[end])
  17. 			return end;
  18. 		else if (a[begin] > a[midi])
  19. 			return begin;
  20. 		else
  21. 			return midi;
  22. 	}
  23. }
  24. // 快速排序hoare版本
  25. int PartSort1(int* a, int begin, int end)
  26. {
  27. 	int left = begin, right = end;
  28. 	int midi = GetMidi(a, begin, end);
  29. 	Swap(&a[midi], &a[begin]);
  30. 	int keyi = begin;
  31. 	while (left < right)
  32. 	{
  33. 		//right找小
  34. 		while (left < right && a[right] >= a[keyi])
  35. 		{
  36. 			right--;
  37. 		}
  38. 		//left找大
  39. 		while (left < right && a[left] <= a[keyi])
  40. 		{
  41. 			left++;
  42. 		}
  43. 		Swap(&a[left], &a[right]);
  44. 	}
  45. 	//left和right相遇,key和left交换
  46. 	Swap(&a[left], &a[keyi]);
  47. 	keyi = left;
  48. 	return keyi;
  49. }
  50. void QuickSort(int* a, int begin, int end)
  51. {
  52. 	if (begin >= end)
  53. 	{
  54. 		return;
  55. 	}
  56. 	int keyi = PartSort1(a, begin, end);
  57. 	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
  58. 	QuickSort(a, begin, keyi - 1);
  59. 	QuickSort(a, keyi + 1, end);
  60. }
2.挖坑法

思路描述

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

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

代码实现

完整代码
  1. // 快速排序挖坑法
  2. int PartSort2(int* a, int begin, int end)
  3. {
  4. 	int left = begin, right = end;
  5. 	int key = a[begin];
  6. 	int hole = begin;
  7. 	while (left < right)
  8. 	{
  9. 		//right找小
  10. 		while (left < right && a[right] >= key)
  11. 		{
  12. 			right--;
  13. 		}
  14. 		//把a[right]放到a[hole] right 位置就是新的坑位
  15. 		a[hole] = a[right];
  16. 		hole = right;
  17. 		//left找大
  18. 		while (left < right && a[left] <= key)
  19. 		{
  20. 			left++;
  21. 		}
  22. 		//把a[left]放到a[hole] left 位置就是新的坑位
  23. 		a[hole] = a[left];
  24. 		hole = left;
  25. 	}
  26. 	a[hole] = key;
  27. 	return hole;
  28. }
  29. void QuickSort(int* a, int begin, int end)
  30. {
  31. 	if (begin >= end)
  32. 	{
  33. 		return;
  34. 	}
  35. 	int keyi = PartSort2(a, begin, end);
  36. 	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
  37. 	QuickSort(a, begin, keyi - 1);
  38. 	QuickSort(a, keyi + 1, end);
  39. }
3.前后指针法

思路归纳 
  1. cur遇到比key大的值 ，++cur
  2. cur遇到比key小的值 ，++prev , 交换prev 和 cur 的位置 ++cur
  3. 重复上述步骤 ，直到cur越界
代码实现

完整代码
  1. int GetMidi(int* a, int begin, int end)
  2. {
  3. 	int midi = (begin + end) / 2;
  4. 	if (a[begin] > a[end])
  5. 	{
  6. 		if (a[end] > a[midi])
  7. 			return end;
  8. 		else if (a[midi] > a[begin])
  9. 			return begin;
  10. 		else
  11. 			return midi;
  12. 	}
  13. 	else //a[end]>a[begin]
  14. 	{
  15. 		if (a[midi] > a[end])
  16. 			return end;
  17. 		else if (a[begin] > a[midi])
  18. 			return begin;
  19. 		else
  20. 			return midi;
  21. 	}
  22. }
  23. //快速排序前后指针法
  24. int PartSort3(int* a, int begin, int end)
  25. {
  26. 	int prev = begin, cur = begin + 1;
  27. 	int midi = GetMidi(a, begin, end);
  28. 	Swap(&a[midi], &a[begin]);
  29. 	int keyi = begin;
  30. 	while (cur <= end)
  31. 	{
  32. 		if (a[cur] < a[keyi])
  33. 		{
  34. 			++prev;
  35. 			Swap(&a[prev], &a[cur]);
  36. 		}
  37. 		++cur;
  38. 	}
  39. 	Swap(&a[prev], &a[keyi]);
  40. 	keyi = prev;
  41. 	return keyi;
  42. }
  43. void QuickSort(int* a, int begin, int end)
  44. {
  45. 	if (begin >= end)
  46. 	{
  47. 		return;
  48. 	}
  49. 	int keyi = PartSort3(a, begin, end);
  50. 	//整个数组被分为[begin,keyi-1]  keyi  [keyi+1,end]
  51. 	QuickSort(a, begin, keyi - 1);
  52. 	QuickSort(a, keyi + 1, end);
  53. }
2.3.2.2非递归实现
大致思路

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

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

  1. 循环
  2. 借助栈

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

❓细节

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

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

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

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

代码实现

  1. //Stack.c Stack.h 参考往期博客
  2. //sort.c
  3. //快速排序前后指针法
  4. int PartSort3(int* a, int begin, int end)
  5. {
  6. 	int prev = begin, cur = begin + 1;
  7. 	int midi = GetMidi(a, begin, end);
  8. 	Swap(&a[midi], &a[begin]);
  9. 	int keyi = begin;
  10. 	while (cur <= end)
  11. 	{
  12. 		if (a[cur] < a[keyi])
  13. 		{
  14. 			++prev;
  15. 			Swap(&a[prev], &a[cur]);
  16. 		}
  17. 		++cur;
  18. 	}
  19. 	Swap(&a[prev], &a[keyi]);
  20. 	keyi = prev;
  21. 	return keyi;
  22. }
  23. void QuickSortNonR(int* a, int begin, int end )
  24. {
  25. 	Stack st;
  26. 	StackInit(&st);
  27. 	StackPush(&st, end);
  28. 	StackPush(&st, begin);
  29. 	while (!StackEmpty(&st))
  30. 	{
  31. 		int left = StackTop(&st);
  32. 		StackPop(&st);
  33. 		int right = StackTop(&st);
  34. 		StackPop(&st);
  35. 		int keyi = PartSort3(a, left, right);//*
  36. 		//两个区间 [left,keyi-1] keyi [keyi+1,right] 
  37. 		//判断两段区间 是否需要入栈
  38. 		//如果 区间元素个数还大于一 则该区间还需要排序 那么入栈（先右后左）
  39. 		if (left < keyi-1)
  40. 		{
  41. 			StackPush(&st,keyi - 1);
  42. 			StackPush(&st, left);
  43. 		}
  44. 		if (right > keyi + 1)
  45. 		{
  46. 			StackPush(&st, right);
  47. 			StackPush(&st, keyi + 1);
  48. 		}
  49. 	}
  50. }
  51. //test.c
  52. TestQuickSortNonR()
  53. {
  54. 	int a[] = { 6,1,2,6,7,9,3,4,5,6,10,8 };
  55. 	int b[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
  56.  
  57. 	QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);
  58. 	QuickSortNonR(b, 0, sizeof(b) / sizeof(int) - 1);
  59.  
  60. 	PrintArr(a, sizeof(a) / sizeof(int));
  61. 	printf("\n");
  62. 	PrintArr(b, sizeof(b) / sizeof(int));
  63.  
  64. }
  65. int main()
  66. {
  67. 	TestQuickSortNonR();
  68. 	return 0;
  69. }

测试结果

总结

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

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

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

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

Tips

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

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

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

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

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/614887
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号