//快速排序法

#include<iostream>
#include<cstdlib>
using namespace std;

int part(int s[],int p,int r)   //把大于s[p]的数放一边,小于它的数放一边
{
 int x = s[p];
 int i = p+1;
 int j = r;
 while(true)
 {
  while(s[i] < x && i<=r)  i++;
  while(s[j] > x && j>=1)  j--;
  if(i >=j)
   break;
  int temp = s[i];
  s[i] = s[j];
  s[j] = temp;
 }
 s[p] = s[j];
 s[j] = x;
 return j;
}

void quicksort(int s[],int p,int r)
{
 if(p < r)
 {
  int q = part(s,p,r);
  quicksort(s, p,q-1);
  quicksort(s,q+1,r);
 }
}

int main()
{
 int s[] = {1,5,3,8,4,10,5};
 int p = 0;
 int r= sizeof s/sizeof *s -1;
 cout<<"排序前: "<<endl;
 for(int i=0;i<=r;i++)
  cout<<s[i]<<"  ";
 cout<<endl;
 quicksort(s,p,r);
 cout<<"排序后: "<<endl;
 for(i=0;i<=r;i++)
  cout<<s[i]<<"  ";
 cout<<endl;
}

评论