经典排序算法—-快排

由于很久没有刷题，现在来复习一下快速排序算法。

首先观察一下此图。

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

它的基本思想为：

1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

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

数组大小为：9

int a[] = {20,5,9,10,15,3,21,1,55,50};

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

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

   int a[] = {20,5,9,10,15,3,21,1,55,50};

2. 从高位向低位查找比temp小的数 while( temp<a[j] && j>i) j–;，找到后，数组变化。a[i++] = a[j] 条件i<j

   int a[] = {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]。

贴源代码：

#include<bits/stdc++.h>
using namespace std;
/*
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。  */
int AdjustArray(int s[],int l, int r){
	if(l<r){
		int i = l,j=r;
		int temp = s[l];
		while(i<j){
			//从右向左找出比基准数小的数
			while(s[j]>temp && i<j) j--; 
			if(i<j){
				s[i++] = s[j];
			}
			//从左边向右查找比基准大的数 
			while(s[i]<=temp && j>i) i++;
			if(i<j){
				s[j--]=s[i];
			} 	
		}
		s[i] = temp;
		AdjustArray(s,l,i-1);
		AdjustArray(s,i+1,r);
	}
}
int main (){
	int a[] = {20,5,9,10,15,3,21,1,55,50};
	int n = 10;
	AdjustArray(a,0,9);
	for(int i=0;i<10;i++){
		printf("%d ",a[i]);
	}
	
	
}