简述快速排序

• 快排主要分为挖空法和交换法

快排都是借助函数的递归实现的

1. 挖空法:

主要通过一个外部变量,将该位置的空间腾出来用于之后不满足元素的存放,左右依次交换.
主要思想是通过递归的划分实现问题分解,每次函数查找的是某个目标元素(一般使用的是当前左侧的第一个元素)的实际位置

void quicksort(vector<int> &op,int left,int right){
	if(left>right)return;
	int a=left,b=right,temp=op[left];
	while(a<b){
			while(a<b&&op[b]>=temp)b--;
			op[a]=op[b];
			while(a<b&&op[a]<=temp)a++;
			op[b]=op[a];
		}
	op[a]=temp;//当前面循环结束时找到了temp元素的实际位置,直接填空
	quicksort(op,left,a-1);
	quicksort(op,a+1,right);
}
#python
#<=
def quicksort(op,left,right):
	if(left>right): return
	a=left
	b=right
	temp=op[left]
	while a<b:
		while a<b and op[b]>=temp:
		    b-=1
		op[a]=op[b]
		while a<b and op[a]<=temp:
		    a+=1
		op[b]=op[a]
	op[a]=temp
	quicksort(op,left,a-1)
	quicksort(op,a+1,right)  

#>=
def quicksort(op,left,right):
	if(left>right): return
	a=left
	b=right
	temp=op[left]
	while a<b:
		while a<b and op[b]>=temp:
		    b-=1
		op[a]=op[b]
		while a<b and op[a]<=temp:
		    a+=1
		op[b]=op[a]
	op[a]=temp
	quicksort(op,left,a-1)
	quicksort(op,a+1,right)
		

2. 交换法:

其实与挖空类似,只是这里每次找到一个当前不满足值时是直接与其反面(左侧/右侧)上次查找停止的位置交换元素

void quicksort(vector<int> &op,int left,int right){
	if(left>right)return;//注意这里,容易出错,只有当left>right 时其中的元素个数才为0  才不用继续向下继续进行
	int a=left,b=right,temp=op[left];
	while(a<b){
			while(a<b&&op[b]>=temp)b--;
			while(a<b&&op[a]<=temp)a++;
			if(a<b){
				int center=op[a];
				op[a]=op[b];
				op[b]=center;
			}
		}
	op[left]=op[a];//找到位置之后将此时这个位置的元素放到之前腾出位置的地方处
	op[a]=temp;
	quicksort(op,left,a-1);
	quicksort(op,a+1,right);
}

#python
def quicksort(op,left,right):
    if left>right: return
    a=left
    b=right
    temp=op[left]
    while a<b:
        while(a<b and op[b]>=temp): b-=1
        while(a<b and op[a]<=temp): a+=1
        if a<b:
            center=op[a]
            op[a]=op[b]
            op[b]=center
    op[left]=op[a]
    op[a]=temp
    quicksort(op,left,a-1)
    quicksort(op,a+1,right)