改进partition 算法代码

#include<iostream> 

#include<algorithm>

using namespace std; 

//演示3-way-partition 给定n个数据，将其按第一个数据做分区中枢

//threep返回两个数据，分别为中间段的起始和终止位置下标 

// p中间段起始下标，r是中间段截止下标  

void threep(int a[],int &p,int &r)

 {

  int x=a[p]; 

  int k=p+1;

  while(k<=r)

  {

  if(a[k]<x)swap(a[k++],a[p++]);

  else if(a[k]>x)swap(a[k],a[r--]);

  else k++;

}

 }

 void quicksort(int a[],int left,int right)

 {

  if(left<right)

  {  int lleft=left,rright=right;

  threep(a, lleft,rright);

  quicksort(a,left,lleft-1);

  quicksort(a,rright+1,right);

}

 }

int main()

{

  int n,p,r;

  cin>>n;

  int a[n];

  for(int i=0;i<n;i++)cin>>a[i];  //5 7 5 2  5 8

  p=0;r=n-1;

  threep(a,p,r); 

  for(int i=0;i<n;i++)cout<<a[i]<<" "; 

  cout<<"\np="<<p<<"  r="<<r; 

  // quicksort(a,p,r);

  //for(int i=0;i<n;i++)cout<<a[i]<<" "; 

  return 0;

}