排序算法——快速排序

2024-01-01 22:31:28

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

 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:%d\n", temp);
	//4 递归分组
	quickSort(a, left, L-1);	//左边那一组继续递归
	quickSort(a, R+1, right);	//右边那一组继续递归
}

文章来源:https://blog.csdn.net/qq_59470001/article/details/135329493
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。