温习快排

一.我自己的做法

1.1 代码

#include<stdio.h>
void swap(int *num1,int *num2){
	int temp=*num1;
	*num1=*num2;
	*num2=temp;
}
int op(int a[],int left,int right){
	while(left<right){
		while(left<right){
			if(a[right]<a[left]){
				swap(&a[right],&a[left]);
				break;
			}
			else
				right--;
		}
		while(left<right){
			if(a[right]<a[left]){
				swap(&a[right],&a[left]);
				break;
			}
			else
				left++;
		}
	}
	return left;
}

void quickSort(int a[],int left,int right){
	int length=right-left;
	if(length<=1)
		return;
	int pos=op(a,left,right);
	quickSort(a,left,pos);
	quickSort(a,pos+1,right);
}

int main(){
	int a[100];
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",a+i);
	quickSort(a,0,n-1);
	for(int i=0;i<n;i++)
		printf("%d ",a[i]);
}

1.2 测试

1.2.1 测试数据

9
2 1 3 1 5 4 6 2 3

1.2.2 结果

二.y总的模板

#include<iostream>

using namespace std;
const int N=100;

void swap(int *num1,int *num2){
	int temp=*num1;
	*num1=*num2;
	*num2=temp;
}

void quickSort(int a[],int left,int right){
	if(left>=right)	return;
	int pivot=a[left];
	int l=left-1;
	int r=right+1;
	while(l<r){
		do l++;while(pivot>a[l]);
		do r--;while(pivot<a[r]);
		if(l<r) swap(&a[l],&a[r]);
	}
	quickSort(a,left,r);
	quickSort(a,r+1,right);
}

int main(){
	int a[N];
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",a+i);
	quickSort(a,0,n-1);
	for(int i=0;i<n;i++)
		printf("%d ",a[i]);
	return 0;
}

2.1注意边界问题

如果选用left做pivot，则递归时两个边界分别为r与r+1。

如果选用right做pivot，则递归时两个边界分别为l-1与l。

也就是对称。