快速排序详解

下面这段是全文的重点，对于一个数组，要进行分治处理，那么我们需要知道到底在哪儿进行分割，当然，也可以无脑的二分法，但是这样的话对于一些情况就会产生很不好的效率，而且我们这个也是二分，但是没有对称的分配。

如上图所示，我们对于一段数组，先取最后一个数作为我们分割点，然后黑线向前推进，如果发现黑线后的数比分割点小，那么就丢到前面准备的一个位置，也就是那一句swap(a[i],a[j]); 在此过程中++i是必不可少的，这样到了最后，在i之前的就都是分割点小，比分割点大的都在i后面，然后把分割点跟i的下一个位置置换，那么不论前后多少个书，分割点的位置是确定的。剩下的只要分治分割点前后的两段数组罢了！等到最后无法继续分割了，就意味着分治完毕，排序完成!

int Partition(int a[],int p,int r)
{
    int ZhuYuan=a[r];
    int i=p-1;
    for (int j=p; j < r; ++j)
    {
 if(a[j]<=ZhuYuan)
 {
     ++i;
     ++times;
     swap(a[i],a[j]);
 }
    }
    swap(a[i+1],a[r]);
    return i+1;
}

void Quick_Sort(int a[],int p,int r)
{
    if (p
下面看效果吧！！

int main()
{
    int a[101];
    for (int i = 0; i<100; ++i)
    {
 a[i]=rand()%1000;
    }
    Quick_Sort(a,0,100);
    for(int s=1;s<100;++s)
    {
 if(s%8==0)
     cout<

完整代码奉上：
#include
#include
using namespace std;

void swap(int &a,int &b)
{
    int tmp=a;
    a=b;
    b=tmp;
}

int times=0;
int Partition(int a[],int p,int r)
{
    int ZhuYuan=a[r];
    int i=p-1;
    for (int j=p; j < r; ++j)
    {
 if(a[j]<=ZhuYuan)
 {
     ++i;
     ++times;
     swap(a[i],a[j]);
 }
    }
    swap(a[i+1],a[r]);
    return i+1;
}

void Quick_Sort(int a[],int p,int r)
{
    if (p
  正文之后

相对来说，快速排序代码比较简单，对于数据结构的要去不高，只要你能理解分治的概念，并且对于数组有着较好的把握，那么应该就很好理解了！