快速排序

版权声明：本文部分为CSDN博主「nrsc」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/nrsc272420199/article/details/82587933快速排序,说白了就是给基准数据找其正确索引位置的过程.

 如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组，设两个指示标志:low指向起始位置，high指向末尾.

 首先从后半部分开始，如果扫描到的值大于基准数据就让high减1,如果发现有元素比该基准数据的值小(如上图中18<=tmp)，就将high位置的值赋值给low位置 ,结果如下:

 然后再开始从后向前扫描,原理同上,发现上图11<=tmp,则将left位置的值赋值给high位置的值,结果如下:

 这样一遍走下来,可以很清楚的知道,其实快速排序的本质就是把基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置.
  以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

以下是我参照啊哈算法实现的代码：

#include<iostream>
#include<stdio.h>
using namespace std;
int a[101],n;
void ptr_sort(int low,int high){
     int i,j,tmp,t;
     if(low>high)
         return;
      tmp=a[low];                 //a[low]作为基数
      i=low;
      j=high;
      while(i!=j)
      {
          while(a[j]>=tmp&&i<j)   //右边开始移动找基数他小的数
          {
              j--;
          }
          while(a[i]<=tmp&&i<j) //左边开始移动找比基数大的数
          {
              i++;
          }
            t=a[i];
            a[i]=a[j];         //交换位置
            a[j]=t;

      }
      a[low]=a[i];            //相遇的数作为基数
      a[i]=tmp;
      ptr_sort(low,i-1);      //左半部分
      ptr_sort(i+1,high);     //右半部分
}
int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];          //输入
    }
    ptr_sort(0,n-1);        //从小到大排序
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";   //输出
    }

}