C++快排_牛客博客

ps:图片来自百度。
快排在应试的时候有可能会被拿出来当考题，所以说有必要去学习。
c++实现:
#include<bits/stdc++.h>
using namespace std;
void Swap(int &a,int &b){
	if(a==b)
	return ;                                    //交换
	a=a+b;
	b=a-b;
	a=a-b;
}
void Q_sort(int a[],int head,int tail){     //数组a的地址,head:第一个元素下标，tail:最后一个元素下标
    if(tail<=head)                           	//这时候已经是有序的
        return;
        
    int pivot=a[head];                        	//轴：pivot.为第一个元素下标
    int left=head+1;                         	//left：第二个元素的下标
    int right=tail;
    
    
    while(left<=right){
        while(right>=left&&a[right]>pivot)    //从右往左找，元素大于轴的值，则跳过，right值减1，(继续往左找)
            right--;                          //直到找到一个比head小的,退出，这时候right停在了那个元素的下标
											  //while要保证left值小于等于right值


	while(left<=right&&a[left]<pivot) 	  //从左往右找，元素小于轴的值，则跳过，left值减1，(继续往右找)
            left++;                           //直到找到一个比head大的,退出，这时候left停在了那个元素的下标
											  //while要保证left值小于等于right值
											  
        if(left>=right)                  	  //已经是相对有序(较大的在右边，较小的在左边)，不用交换
            break;

        Swap(a[left],a[right]);          //交换：之前找到的往右小于轴的值，和，之前找到的往左大于轴的值。

        left++,right--;                       //缩进一位，继续找。
    }
    
    
       a[head]=a[right];               //跳出while的时候，没有缩进，right位置就是右边第一个小于轴的，

	a[right]=pivot;                    //left的位置就是左边第一个大于轴的
		                      //这时候把右边那个小于轴的值当做下次排序的轴，并把上次的轴放在right那里
    
    Q_sort(a,head,right-1);               //a[head](上次的a[right])为下次(左边)的轴，左半部分继续排序(递归)
    Q_sort(a,left,tail);                   //a[left]为下次(右边)的轴，右半部分继续排序
}
int main(){
	int a[100];
	int n;
	cout<<"请输入数组元素数量"<<endl;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	Q_sort(a,0,n-1);
	for(int i=0;i<n;i++){
	   cout<<a[i]<<" ";
	}
	return 0;
}