快速排序,说白了就是给基准数据找其正确索引位置的过程.
如下图所示,假设最开始的基准数据为数组第一个元素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]<<" "; //输出
}
}