• 排序算法——快速排序（队列和栈实现非递归）

    一、背景 

    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。本博客以hoare版本为例

    二、实现

    1、hoare版本


     

    老规矩我们先写单趟：

    以最左边元素为基准：右边先走，找到左边大于key的数，右边小于key的数：

    1. int key = left;
    2. int begin = left;
    3. int end = right - 1;
    4. while (a[end] >= a[key])//在右边找到第一个比key小的值
    5. {
    6. 	end--;
    7. }
    8. while(a[begin] <= a[key])//在左边找到第一个比key大的值
    9. {
    10. 	begin++;
    11. }
    12. swap(&a[begin], &a[end]);

    相遇时说明第一趟排好，所以我们可以写出如下代码：

    1. int PartSort1(int* a, int left, int right)
    2. {
    3. 	int key = left;
    4. 	int begin = left;
    5. 	int end = right - 1;
    6. 	while (begin < end);
    7. 	{
    8. 		
    9. 		while (a[end] >= a[key])//在右边找到第一个比key小的值
    10. 		{
    11. 			end--;
    12. 		}
    13. 		while (a[begin] <= a[key])//在左边找到第一个比key大的值
    14. 		{
    15. 			begin++;
    16. 		}
    17. 		swap(&a[begin], &a[end]);
    18. 	}
    19. 	
    20. }

    剩下的排序类似树的左右子树遍历用递归实现：
    递归结束条件为剩余长度<=1（也可以写成right<=left），注意在经行找值的时候，还要保持左小于右。

    1. void QuickSort(int* a, int left, int right)
    2. {
    3. 	if (right-left<=1)
    4. 	{
    5. 		return;
    6. 	}
    7. 	int key = left;
    8. 	int begin = left;
    9. 	int end = right;
    10. 	while (begin < end)
    11. 	{
    12. 		while (begin < end && a[end] >= a[key])//在右边找到第一个比key小的值
    13. 		{
    14. 			--end;
    15. 		}
    16. 		while (begin < end && a[begin] <= a[key])//在左边找到第一个比key大的值
    17. 		{
    18. 			++begin;
    19. 		}
    20. 		swap(&a[begin], &a[end]);
    21. 	}
    22. 	swap(&a[begin], &a[key]);
    23. 	key = begin;
    24. 	QuickSort(a, left, key-1);
    25. 	QuickSort(a, key+1, right);
    26. }

    2、挖矿法

    选择一个基准值，仍然通过begin和end指针来操作

    首先，我们仍然是从end开始向前找一个小于28的数，找到后直接放在begin的位置，注意这里不是交换，如下图：

    箭头所指向的是我们选取的基准值，这时可以理解为它不在这个数列当中，而end对应的位置就出现了一个坑，这时，begin开始向后寻找，找到第一个大于基准值的数后放到end的位置，如下图

    此时，begin的位置又会出现一个坑，这时再次让end向前移动继续找第一个小于基准值的数，放到begin的位置，再使begin向后移动找第一个大于基准值的数，重复此操作直到begin和end相遇，这时，把基准值放到该位置。这样，一趟快速排序结束，如下图

     代码实现：

    1. void QuickSort(int* a, int left, int right)
    2. {
    3. 	if (right - left <= 1)
    4. 	{
    5. 		return;
    6. 	}
    7. 	int key = left;
    8. 	int begin = left;
    9. 	int pit = left;//坑
    10. 	int end = right;
    11. 	while (begin < end)
    12. 	{
    13. 		while (begin < end && a[end] >= a[key])//在右边找到第一个比key小的值
    14. 		{
    15. 			end--;
    16. 		}
    17. 		a[pit] = a[end];//放入坑中
    18. 		pit = end;//坑更新
    19. 		while (begin < end && a[begin] <= a[key])//在左边找到第一个比key大的值
    20. 		{
    21. 			++begin;
    22. 		}
    23. 		a[pit] = a[begin];
    24. 		pit = begin;
    25. 	}
    26. 	a[pit] = a[key];//最后将key放入坑中
    27. 	QuickSort(a, left, begin-1);
    28. 	QuickSort(a, begin+1, right);
    29. }

    3、前后指针法

     

    前后指针法：
    第一步：选最右边的值做key（key是单趟排序后能排到最后该待的位置的数据）
    第二步：cur开始找，cur遇到比key小或相等的，cur和prev交换，cur和prev一起向右走。cur遇到比key大的，cur向右走，prev不动。一直循环第二步（若cur走出了数组，结束）

    还是先写单趟

    1.  
    2. int key = left;
    3. int pre = left;
    4. int cur = left + 1;
    5. while (cur <= right - left + 1)
    6. {
    7. 	if (a[cur] < a[key] && ++pre != cur)//pre加后如果与cur相等为自己与自己交换
    8. 	{
    9. 		swap(&a[cur], &a[pre]);//交换后要cur++，大于也++，所以直接出判断++
    10. 	}
    11. 	cur++;
    12. }
    13. swap(&a[key], &a[pre]);

    当出现自己于自己交换时可以不用交换，因为交不交换都要cur++所以直接在if后面++ 

    整体代码：

     

    1. void QuickSort(int* a, int left, int right)
    2. {
    3. 	/*if (right - left <= 1)
    4. 	{
    5. 		return;
    6. 	}*/
    7. 	 //小区间优化，不再递归分割排序，减少递归的次数
    8. 	if ((right - left + 1) < 10)
    9. 	{
    10. 		InsertSort(a + left, right - left + 1);//这一定要加left
    11. 	}
    12. 	else
    13. 	{
    14. 		int mid = findmid(a, left, right);
    15. 		swap(&a[left], &a[mid]);
    16. 		int key = left;
    17. 		int pre = left;
    18. 		int cur = left + 1;
    19. 		while (cur <= right - left + 1)
    20. 		{
    21. 			if (a[cur] < a[key] && ++pre != cur)//pre加后如果与cur相等为自己与自己交换
    22. 			{
    23. 				swap(&a[cur], &a[pre]);//交换后要cur++，大于也++，所以直接出判断++
    24. 			}
    25. 			cur++;
    26. 		}
    27. 		swap(&a[key], &a[pre]);
    28. 		int key = pre;
    29. 		QuickSort(a, left, key - 1);
    30. 		QuickSort(a, key+ 1, right);
    31. 	}
    32. }

    三、优化：

    1、避免重复选择

     插入排序时间复杂度为O（nlogn）（每一层n个值，树的高度为logn）

    但是对于我们刚刚实现的版本如果一个数列已经排好了，但是代码任然会一个一个比较;

    所以我们接下来重点考虑其怎么优化？最佳的答案为三数取中原则：即给定三个数取不大不小的那个，这样会大大减少在循环中比较的次数。从而提高效率：
    代码实现：

    1. lfindmid(int* a, int left, int right)
    2. {
    3. 	int midi = (left + right) / 2;
    4. 	// left midi right
    5. 	if (a[left] < a[midi])
    6. 	{
    7. 		if (a[midi] < a[right])
    8. 		{
    9. 			return midi;
    10. 		}
    11. 		else if (a[left] < a[right])
    12. 		{
    13. 			return right;
    14. 		}
    15. 		else
    16. 		{
    17. 			return left;
    18. 		}
    19. 	}
    20. 	else // a[left] > a[midi]
    21. 	{
    22. 		if (a[midi] > a[right])
    23. 		{
    24. 			return midi;
    25. 		}
    26. 		else if (a[left] < a[right])
    27. 		{
    28. 			return left;
    29. 		}
    30. 		else
    31. 		{
    32. 			return right;
    33. 		}
    34. 	}
    35. }
    36. void QuickSort(int* a, int left, int right)
    37. {
    38. 	if (right - left <= 1)
    39. 	{
    40. 		return;
    41. 	}
    42. 	int key = findmid(a, left, right);
    43. 	int begin = left;
    44. 	int pit = left;//坑
    45. 	int end = right;
    46. 	while (begin < end)
    47. 	{
    48. 		while (begin < end && a[end] >= a[key])//在右边找到第一个比key小的值
    49. 		{
    50. 			end--;
    51. 		}
    52. 		a[pit] = a[end];
    53. 		pit = end;
    54. 		while (begin < end && a[begin] <= a[key])//在左边找到第一个比key大的值
    55. 		{
    56. 			++begin;
    57. 		}
    58. 		a[pit] = a[begin];
    59. 		pit = begin;
    60. 	}
    61. 	a[pit] = a[key];
    62. 	QuickSort(a, left, begin-1);
    63. 	QuickSort(a, begin+1, right);
    64. }

    2、时间优化

    对于一颗树来说最后几层几乎占了大部分的数据，例如：

    对于排好五个数如果我们用递归实现则需要递归6次这是非常麻烦的，所以我们最好用插入排序去实现剩余部分的排序：

    1. lfindmid(int* a, int left, int right)
    2. {
    3. 	int midi = (left + right) / 2;
    4. 	// left midi right
    5. 	if (a[left] < a[midi])
    6. 	{
    7. 		if (a[midi] < a[right])
    8. 		{
    9. 			return midi;
    10. 		}
    11. 		else if (a[left] < a[right])
    12. 		{
    13. 			return right;
    14. 		}
    15. 		else
    16. 		{
    17. 			return left;
    18. 		}
    19. 	}
    20. 	else // a[left] > a[midi]
    21. 	{
    22. 		if (a[midi] > a[right])
    23. 		{
    24. 			return midi;
    25. 		}
    26. 		else if (a[left] < a[right])
    27. 		{
    28. 			return left;
    29. 		}
    30. 		else
    31. 		{
    32. 			return right;
    33. 		}
    34. 	}
    35. }
    36. void QuickSort(int* a, int left, int right)
    37. {
    38. 	if (right - left <= 1)
    39. 	{
    40. 		return;
    41. 	}
    42. 	// 小区间优化，不再递归分割排序，减少递归的次数
    43. 	if ((right - left + 1) < 10)
    44. 	{
    45. 		InsertSort(a + left, right - left + 1);//这一定要加left
    46. 	}
    47. 	int key = findmid(a, left, right);
    48. 	int begin = left;
    49. 	int pit = left;//坑
    50. 	int end = right;
    51. 	while (begin < end)
    52. 	{
    53. 		while (begin < end && a[end] >= a[key])//在右边找到第一个比key小的值
    54. 		{
    55. 			end--;
    56. 		}
    57. 		a[pit] = a[end];
    58. 		pit = end;
    59. 		while (begin < end && a[begin] <= a[key])//在左边找到第一个比key大的值
    60. 		{
    61. 			++begin;
    62. 		}
    63. 		a[pit] = a[begin];
    64. 		pit = begin;
    65. 	}
    66. 	a[pit] = a[key];
    67. 	QuickSort(a, left, begin-1);
    68. 	QuickSort(a, begin+1, right);
    69. }

    四、hoare版的相关证明：   

    hoare版中比较让人难以理解的是为什么最后相遇时值比key小。（其次hoare规定如果让左边做key，那么右边一点要先走），相关证明如下：



     

    五、非递归两种实现方法

    将递归改为非递归一共有两种办法：
    1、是通过栈来模拟实现递归，2、是直接通过循环来实现

    而快速排序最好的办法是用栈来模拟实现：

    众所周知，栈的特性是先进后出，我们拿数组arr=[5,2,4,7,9,1,3,6]来举栗子。
    第一步：我们先把区间的右边界值7进行压栈，然后把区间的左边界值0进行压栈，那我们取出时就可以先取到左边界值，后取到后边界值

    第二步：我们获取栈顶元素，先取到0给left，后取到7给right，进行单趟排序


    第三步：第一趟排完后，区间被分为左子区间和右子区间。为了先处理左边，所以我们先将右子区间压栈，分别压入7和5，然后压入左子区间，3和0


    第四步：取出0和3进行单趟排序


    第五步：此时左子区间又被划分为左右两个子区间，但是右子区间只有4一个值，不再压栈，所以只入左子区间，将1和0压栈

    第六步：取出0和1进行单趟排序


    至此，左子区间全部被排完，这时候才可以出5和7排右子区间，这个流程其实和递归是一模一样的，顺序也没变，但解决了递归的致命缺陷——栈溢出。后面的流程就不一一展现了

     

    1. void QuickSortNonR(int* a, int left, int right)
    2. {
    3. 	Stack st;
    4. 	StackInit(&st);
    5. 	StackPush(&st, right);//先入右，再入左
    6. 	StackPush(&st, left);
    7. 	while (!StackEmpty(&st))//栈为空说明区间排完了
    8. 	{
    9. 		int begin = StackTop(&st);// 取的时候为先左后右
    10. 		StackPop(&st);
    11. 		int end = StackTop(&st);
    12. 		StackPop(&st);
    13. 		int key = PartSort1(a, begin, end);
    14. 		if (key + 1 < end)//如果右存在先压右
    15. 		{
    16. 			StackPush(&st, end);
    17. 			StackPush(&st, key + 1);
    18. 		}
    19. 		if (key - 1 > begin)//如果左存在先压左
    20. 		{
    21. 			StackPush(&st, key - 1);
    22. 			StackPush(&st, begin);
    23. 		}
    24. 	}
    25. 	StackDestroy(&st);
    26. }

    那么我们是否可以通过队列来实现呢？当然是可以的只不过将类似前序遍历，改成了层序遍历。

     

    1. void QuickSortNonR2(int* a, int left, int right)
    2. {
    3. 	Queue qe;
    4. 	QueueInit(&qe);
    5. 	QueuePush(&qe, left);//先进先出先加左边
    6. 	QueuePush(&qe, right);
    7. 	while (!QueueEmpty(&qe))
    8. 	{
    9. 		int begin = QueueFront(&qe);
    10. 		QueuePop(&qe);
    11. 		int end = QueueFront(&qe);
    12. 		QueuePop(&qe);
    13. 		int key = PartSort1(a, begin, end);
    14. 		if (key - 1 > begin)//如果左存在先压左
    15. 		{
    16. 			QueuePush(&qe, begin);
    17. 			QueuePush(&qe, key - 1);
    18. 		}
    19. 		if (key + 1 < end)//如果右存在先压右
    20. 		{
    21. 			QueuePush(&qe, key + 1);
    22. 			QueuePush(&qe, end);
    23. 		}
    24. 	}
    25. 	QueueDestroy(&qe);
    26.  
    27. }

     

  • 相关阅读:
    【微软漏洞分析】MS15-010 CNG 安全功能绕过漏洞 - CVE-2015-0010
    基于 SaaS 搭建的党建小程序源码系统 带完整的搭建教程
    java基于springboot的社区生活超市管理系统
    【一起学Rust · 项目实战】命令行IO项目minigrep——重构优化模块和错误处理
    回归与聚类算法系列⑤：逻辑回归
    Oracle PrimaveraUnifier空间管理器(Space Manager)
    【数据结构】基础：队列（C语言）
    模拟 Junit 框架
    Spring——依赖注入
    ClickHouse 物化视图
  • 原文地址：https://blog.csdn.net/suiyi_freely/article/details/139334627