快速排序（y总模板＋边界问题）

快速排序（修改版，由于上次发的快速排序存在边界问题没有讨论，所以这次重新发）

y总代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>

using namespace std;

void quick_sort(int *arry,int low,int high)
{
	if(low>=high)
	return;
	
	int i=low-1,j=high+1,x=arry[low+high>>1];
	
	while(i<j)
	{
		do i++;while(arry[i]<x);
		do j--;while(arry[j]>x);
		
		if(i<j) swap(arry[i],arry[j]);
	} 
	
	quick_sort(arry,low,j);
	quick_sort(arry,j+1,high);
}
int main()
{
	int num[10]={12,56,96,1,-1,32,56,4,89,5};
	quick_sort(num,0,9);
	
	for(int i=0;i<10;i++)
	printf("%d ",num[i]);
}

边界问题

前言
昨天想了一天，因为边界问题，一直导致我 AC 不了ACwing快速排序。然后看了看昨天发布的快速排序，并没有讨论边界问题。其实在这里边界问题是很重要的。

具体问题
(1)假如我们要排序 一个序列，然后选择的基准值是左右两个端点。我们会发现，在刚刚开始寻找 i 或者 j 哨兵的位置的时候，就会在我们选择的端点处卡住。

(2)如果我们选择左端点为基准数，我们的 i 哨兵会卡在左端点处，quick_sort(q,l,i-1)这时候，l>=i-1,这个函数return。但是quick_sort(q,i,r),由于 i 的位置在第一个，所以无限循环调用本身这个函数。

(3)同理，当我们选择右端点,quick_sort(q,l,j),quick_sort(q,j+1,r),我们发现 j==r，但是后面这个 quick_sort(q,j+1,r) j+1>=r, 所以return。但是前面一个 quick_sort(q,l,j)一直是对原来这个区间排序，所以这里也会陷入死循环。

解决办法

直接模拟对两个数据的数组排序
例：{6，20}
如果基准点为 x = q[ l + r >> 1 ]
while( i < j ) 那么我们 quick_sort ( q, l , j) quick_sort( q, j+1, r)

如果基准点为 x = q [ l + r + 1 >> 1]
while( i < j ) 那么我们 quick_sort( q, l,i-1) quick_sort( q, i,r)

顺便提一下，如果循环条件是 while( i <= j)
这时候我们需要反过来，左端点用 i ，右端点用 j。

最后这就是对昨天快速排序的总结，如果实在是不懂边界问题，那么，就记住y总给的模板。

最后

以上就是俏皮板栗最近收集整理的关于快速排序（y总模板＋边界问题）的全部内容，更多相关快速排序（y总模板＋边界问题）内容请搜索靠谱客的其他文章。