关于快速排序算法，由于其有着很好的平均时间复杂度而得到了广泛的应用。
快排的思想：每次从数组中取出一个元素出来，然后将该元素放置到一个合适的位置，使得该元素前面的数都小于或等于该元素，其后面的数都大于或等于该元素。然后在对该元素左右两边的数组进行同样的操作，直到左右两边的元素为空。
比如：有数组：5 3 8 2 6. 取出一个数5， 然后将数组中小于或等于5的数放到5的左边，大于等于5的数放到其右边，然后得到：2 3 5 8 6. 然后在对5左右两边的子数组再进行排序。
根据以上分析，那么通过什么方法来确定取出的元素应当放置的位置呢。在此主要介绍二种方法，
1、严蔚敏版本数据结构中介绍的划分方法
其划分过程如下：
1）将数组的第一个元素取出保存，其值假如为x。并将其第一个位置保存到i。
2）从数组的后面进行遍历，找出第一个小于x的元素，设其下标为j，然后将此元素保存到位置为i的地方。
3）从数组的前面找出第一个大于x的元素，其下标为i,然后将此元素保存到位置为j的地方.
4）若i<j， 则重复步骤2~3, 否则返回i.
其划分代码如下：
int partition2(int arr[], int low, int high)
{
int tmp;
tmp = arr[low];
while(low < high)
{
while(low < high && arr[high] >= tmp)
high--;
arr[low] = arr[high];
//swap(arr[low], arr[high]);
while(low < high && arr[low] <= tmp)
low++;
arr[high] = arr[low];
//swap(arr[low], arr[high]);
}
arr[low] = tmp;
return low;
}
2、算法导论中关于快速排序的划分函数的介绍
其划分过程如下：
1）首先将数组中最后一个元素保存为x。
2）然后从前往后依次比较，若当前元素小于或等于x，则将小于x的元素个数加1，并将当前元素与大于x的第一个元素进行交换。
具体过程见代码。
其划分代码如下：
int partition1(int arr[], int p, int r)
{
int tmp, hel, i, j;
hel = arr[r];
i = p-1;
for(j=p; j<r; j++)
{
if(arr[j] < hel)
{
i++;
swap(arr[i], arr[j]);
}
}
arr[r] = arr[i+1];
arr[i+1] = hel;
return i+1;
}
代码中用到的交换函数swap如下：
inline void swap(int &a, int &b)
{
int tmp;
tmp = a; a = b; b = tmp;
}
快速排序通过每次将一个元素放置到其最终位置，然后将两边的未排序的子数组进行递归。
代码如下：
void qsort(int arr[], int i, int j)
{
int tmp;
if(i < j)
{
tmp = partition2(arr, i, j);
qsort(arr, i, tmp-1);
qsort(arr, tmp+1, j);
}
}
下面写一个测试函数，首先输入数组中元素的个数，然后依次输入每个元素，最后输出排序后的结果。
代码如下：
int main()
{
int arr[102], n, i;
while(scanf("%d",&n)==1)
{
for(i=1; i<=n; i++)
scanf("%d",&arr[i]);
qsort(arr,1, n);
for(i=1; i<=n; i++)
printf("%d ",arr[i]);
printf("
");
}
return 0;
}