数据结构-快速排序 （C++代码）

解题思路:

快速排序最关键的一点就是将整个序列分解：（~~~）a[i] (~~~)

    其中a[i]为序列中任意一项，一般默认为序列第一项，书上把这一项叫做枢轴或者支点。

    假设我们已经有了这样一个partition函数能够做上述这件事，那么接下来我们显然就可以用递归了，因为原序列已经分解成两个小序列了，接下来可以对小序列进行同样操作，直到最后序列变成单个值。

所以最关键就是如何实现partition函数。

    题目已经给了代码，那么我主要说一下关键点帮助不太懂的快速理解：这个函数中所进行的操作的原则是始终要确保high右边的值（不包括high所指的）不小于支点值，low左边值（不包括low所指的）不大于支点值。这样在high移动过程中假如碰到了第一个小于支点值得项x，把该项放置到low所指的位置，然后low+1，其结果就是将x移动到了low左边，然后再从low那边做类似的事，直到完成任务。

注意事项:





参考代码:

#include<iostream> 
using namespace std;

void quick_sort(int a[],int,int);
int partition(int a[],int low,int high);


int main()
{
 int n;
 cin>>n;
 int a[n+1];//保留a[0]作监视哨，很关键。递归时可以多次利用该监视哨
 for(int i=1;i<=n;i++)
  cin>>a[i];
 quick_sort(a,1,n);
 for(int i=1;i<=n;i++)
  cout<<a[i]<<" ";
  cout<<endl;
return 0;
}



void quick_sort(int a[],int low,int high)
{
 if(low<high)
 {
  int pivot=partition(a,low,high);
  quick_sort(a,low,pivot-1);
  quick_sort(a,pivot+1,high);
 }
}


int partition(int a[],int low,int high)
{
 a[0]=a[low];//将支点保存在监视哨中
 while(low<high)
 {
  while(low<high&&a[high]>=a[0])
   high--;
   a[low]=a[high];
  while(low<high&&a[low]<=a[0])
   low++;
   a[high]=a[low];
 }
 a[low]=a[0];
 return low;
}