C++：快速排序



C++：快速排序

 在风口浪尖过了两天，难得今天风平浪静，解放区的天是明朗的天，我Jackill心里好喜欢……只是弄出这么大的动静，实非我所愿，希望从崩溃边缘跑回来的我……希望什么呢？GOOD LUCK吧！
 
    要不怎么说，书到用时方恨少呢，竟然只会一种冒泡排序，赶紧翻出传说多年的数据结构一眼便像中了快速排序，简单的给个思路吧：
 
    快速排序就好比是有一队大小不等的球，先选择一个作为标准，然后有两个人分别从开头和结尾往中间走，分别将身边的球和标准球比较，例如结尾的那个人将比自己球小的那个便扔到对方那边去，等到两个人碰头之后，再将标准球插入到两个人所占的位置，接着再对两边分别进行同样的步骤；写个代码如下：
 
void swap(int a[],int left,int right) //交换数组的数据；
{
 int temp;
 temp=a[left];
 a[left]=a[right];
 a[right]=temp;
}
void quicksort(int a[],int left,int right)
 {
 if(left>=right) return;
 int pivot=(left+right)/2;  //标准球为中间那个；
 swap(a,pivot,right);       //将标准球放到队伍最后
 pivot=partition(a,left,right);//同时开始往中间走，往两边扔球；
 sort(a,left,pivot-1);  //递归
 sort(a,pivot+1,right); //递归
}
int partition(int a[],int left,int right)
{
int i=left;
int j=right;
int temp=a[j];               //选择好的标准球
while(i!=j)
{
  while((a[i]<temp)&&(i<j)) i++;  //左边的球大甩到右边那
  if(i<j)
  {
  a[j]=a[i];
  j–;
  }
  while(a[j]>temp && i<j) j–;    //比标准球小甩去左边
  if(i<j)
  {
  a[i]=a[j];
  i++;
  }
}
a[i]=temp;    //将标准球插入到碰面的位置，划分出两个队列来；
return i; 
}
http://blog.sina.com.cn/s/blog_48db23f6010006xt.html