w6 T325337 【模板】快速排序

主要思路：整体思路就是把<num[mid]的元素扔到mid左边，把>num[mid]的元素扔到mid右边，然后用同样的方法对mid左边和右边的序列进行处理。在代码实现上我使用了双指针。

以样例为例：

num[0]=4 num[1]=2 num[2]=4 num[3]=5 num[4]=1

mid=num[2] 第一次处理后：1 2 4 5 4

mid_left=num[0]，mid_right=num[3] 第二次处理后：1 2 4 4 5

代码实现如下：

#include<iostream>
#include<algorithm>
using namespace std;
int n,num[100005];

void QuickSort(int A[],int l,int r){
　　int i=l,j=r,mid=A[l+(r-l)/2];
　　while(i<=j){
　　　　while(A[i]<mid) i++; //找到比mid大的元素的下标
　　　　while(A[j]>mid) j--; //找到比mid小的元素的下标
　　　　if(i<=j){
　　　　　　swap(A[i],A[j]); //交换之前找到的两个元素
　　　　　　i++;
　　　　　　j--;
　　　　}
　　}
　　if(i<r) QuickSort(A,i,r); //递归，对mid右边的序列进行处理
　　if(l<j) QuickSort(A,l,j); //递归，对mid左边的序列进行处理
}

int main()
{
　　cin>>n;
　　for(int i=0;i<n;++i) cin>>num[i]; //输入序列
　　QuickSort(num,0,n-1); //快速排序
　　for(int i=0;i<n;++i) cout<<num[i]<<" "; //输出排序后的数列
　　cout<<endl;
　　return 0;
}

搜索

复制