//快速排序（递归版）
void QSort(int* a,int left,int right)
{
int tmp = a[left];
int p = left;
int i = left,j = right;
while(i<=j)
{
//升序
{
while(a[j]>=tmp && j>=p)
j--;
if(j>=p)
{
a[p] = a[j]; //比划分元小的交换到左边
p = j;
}
while(a[i]<=tmp && i<=p)
i++;
if(i<=p)
{
a[p] = a[i]; //比划分元大的交换到右边
p = i;
}
}
//降序
{
while(a[j]<=tmp && j>=p)
j--;
if(j>=p)
{
a[p] = a[j]; //比划分元大的交换到左边
p = j;
}
while(a[i]>=tmp && i<=p)
i++;
if(i<=p)
{
a[p] = a[i]; //比划分元小的交换到右边
p = i;
}
}
}
a[p] = tmp;
if(p-left>1)
QSort(a,left,p-1);
if(right-p>1)
QSort(a,p+1,right);
}
//快速排序（非递归版）
int Partition(int* a,int left,int right)
{
int pivot = a[right];
while(left<right)
{
//升序
{
while(a[left]<pivot && left<right)
left++;
if(left<right)
a[right--] = a[left];
while(a[right]>pivot && left<right)
right--;
if(left<right)
a[left++] = a[right];
}
//降序
{
while(a[left]>pivot && left<right)
left++;
if(left<right)
a[right--] = a[left];
while(a[right]<pivot && left<right)
right--;
if(left<right)
a[left++] = a[right];
}
}
a[left] = pivot;
return left;
}