排序算法——快速排序

先取一个中间值，将该值临时保存，将两个指针指向最左边元素和最右边元素。左右指针指向元素依次和中间值比较，判断左指针指向元素是否小于中间值，是，则左指针右移；否，则左指针指向元素覆盖右指针指向元素，然后判断右指针元素是否大于中间值，是，则右指针左移；否，则右指针指向元素覆盖左指针指向元素。两边指针依次与中间值判断，相向而行，直到两个指针指向同一个位置，把中间值放回到该位置。此时，数据分成左右两组，左边数据小于中间值，右边数据大于中间值（左边的最大的那个要小于右边的最小的那个），然后无限分下去，直到不可拆分为止（递归）

 66		43		89		98		12		18		15		23		33		50
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
left																   right     
//假设a[left]是中间数据，临时保存，然后判断大小，循环挪动L和R并覆盖
	//由于初始中间值取左指针指向元素，则先由右指针指向元素比较，50<66，则覆盖
 50		43		89		98		12		18		15		23		33		50
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 L																   		 R  
	//轮到左指针指向元素判断，43<66，则左指针右移，89>66，则元素覆盖到右指针位置
 50		43		89		98		12		18		15		23		33		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 				 L													     R
	//轮到右指针指向元素判断，89>66，则右指针左移，33<66，则元素覆盖到左指针位置
 50		43		33		98		12		18		15		23		33		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 				 L												 R
	//轮到左指针指向元素判断，33<66，则左指针右移，98>66，则元素覆盖到右指针位置
 50		43		33		98		12		18		15		23		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 				 		 L										 R     
	//轮到右指针指向元素判断，98>66，则右指针左移，23<66，则元素覆盖到左指针位置
 50		43		33		23		12		18		15		23		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 				 		 L								 R        
	//轮到左指针指向元素判断，23<66，则左指针右移，12<66，则元素覆盖到右指针位置     
 50		43		33		23		12		18		15		12		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 				 		 		 L						 R    
	//轮到右指针指向元素判断，12<66，则元素覆盖到左指针位置
 50		43		33		23		12		18		15		12		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 				 		 		 L				         R  
	//轮到左指针指向元素判断，12<66,18<66,15<66,左指针右移到左右指针指向同一位置后中间值覆盖该位置元素
 50		43		33		23		12		18		15		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
 				 		 		 				        LR      
//此时以左右指针重合处为分界点，将已有元素分为两组，两组继续上述排序，然后递归分组直到无法分组为止
	//left到L-1为一组，R+1到right为一组
 50		43		33		23		12		18		15		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
left				 		 		 		    L-1	            R+1    right  

代码：     
//快速排序
void quickSort(int* a, int left, int right){
	//0或者5 递归结束
	if (left >= right) return;
	//1 先假设a[left]是中间数据,并临时保存
	int temp = a[left];
	int L = left;
	int R = right;
	//2 循环挪动l和r并覆盖  循环结束后 L==R
	while (L < R){
		//2.1 先挪右边的
		while (L<R && a[R]>temp) R--;
		a[L] = a[R];
		//2.2 再挪左边的
		while (L<R && a[L]<temp) L++;
		a[R] = a[L];
	}
	//3 用中间数据覆盖回来
	a[R] = temp;//a[L]=temp;
	printf("mid:%dn", temp);
	//4 递归分组
	quickSort(a, left, L-1);	//左边那一组继续递归
	quickSort(a, R+1, right);	//右边那一组继续递归
}

代码007普通

打赏 收藏 海报 链接