蓝桥杯算法提高-快速排序-题解（C++代码）详细

 首先观察一下此图。

观察此图我们可以得出，快排是选择基准数 + 分治。 

 它的基本思想为：

 1．先从数列中取出一个数作为基准数。

 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

 3．再对左右区间重复第二步，直到各区间只有一个数。 

 接下来我们以该数组为例子： 数组大小为：9

{20,5,9,10,15,3,21,1,55,50};

我们先观察第一次分区。0 - 9的分区.l = 0 r = 9

1.取基准数temp = a[ l ];

{20,5,9,10,15,3,21,1,55,50}

2.从高位向低位查找比temp小的数 while( temp

 {1,5,9,10,15,3,21,1,55,50}

3.从低位位向高位查找比temp大的数while( temp>=a[i] && i<j) i++，找到后，数组变化。填入a[j--] = a[i] 条件要i<j

{1,5,9,10,15,3,21,21,55,50};

此时i<j 已经不成立，不能再往下继续查找。此时将基准数还原到数组中s[i] = temp;或 s[j] = temp。查找的结束条件 i==j 了。另外：i + j = 9分区大小。

第一次分区结果

{1,5,9,10,15,3,20,21,55,50}

继续重复1 - 3步骤

while( temp<a[j] && j>i) j--; 解读，高位向低位查找，a[j]比temp大继续往前找，直到temp>a[j]。

贴源代码：

#includeusing namespace std;
/*
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。  */
const int N = 1e5+1;
int a[N]={0};
int n;
void quick_sort(int l, int r){
	
	if(l<r){
		int i = l;
		int j = r;
		int temp = a[l];
		while(i<j){
			//从右往左找比temp小的数 
			while(i<j && temp<=a[j]) j--;
			if(i<j){
				a[i++] = a[j];
			}
			while(ia[i]) i++;
			if(i<j){
				a[j--] = a[i];
			}
			
		}
		a[i] = temp;
		quick_sort(l,i-1);
		quick_sort(i+1,r);	
	}
}
//20 5 9 10 15 3 21 1 55 50
int main (){

	while(1){
		scanf("%d",&a[n]);
		if(a[n]==0){
			break;
		}
		n++;
	}
	quick_sort(0,n-1);
	for(int i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	return 0;
	 
}

myblog：momoc.xyz