快速排序采用递归、分治的思想。
基本思路是：选待排序元素集合的某一元素作分隔数，将集合分为两组(一组比分隔数小，另一组则大于等于分隔数)，然后分别对每组递归此过程。

简单说来，步骤如下：

代码如下：

//--------------------------------------------------------------------------------------
// @File: quickSort.cpp
//
// @Desc: 实现快速排序
//
// @Version $ 2009-09-26 14:00:00 OutSky $
// @Copyright (c) OutSky	www.outsky.org
//--------------------------------------------------------------------------------------

#include <iostream>
using namespace std;


//--------------------------------------------------------------------------------------
// @Name: quickSort
// 
// @Desc: 对可比较大小元素数组进行快速排序（由小到大）
//
// @Param: T    :   元素的类型
//         array:   要排序的数组
//         low  :   排序部分的开始下标
//         high :   排序部分的结尾下标
//
// @Return: void
//
// @Notice: 元素类型T必须可比较，即必须实现'>/</=='此类运算符
//--------------------------------------------------------------------------------------
template <class T>
void quickSort(T *const array, const int low, const int high)
{
    if(NULL == array)
    {
        return ;
    }

    // 递归的结束条件
    if(low >= high)
    {
        return ;
    }
    else
    {
        const T separateNum = array[low];     // 保存数组的首元素，作为分隔比较元素
        int curLow = low+1;                   // 保存低下标
        int curHigh = high;                   // 保存高下标
        
        // 一分为二
        while(true)
        {
            // 移动到第一个比separateNum大的元素
            while(curLow<high && separateNum>=array[curLow])
            {
                ++curLow;
            }

            // 移动到第一个比separateNum小的元素
            while(curHigh>low && separateNum<array[curHigh])
            {
                --curHigh;
            }

            // 如果相遇，则break
            if(curLow >= curHigh)
            {
                break;
            }
            // 否则，交换
            else
            {
                const T temp = array[curLow];
                array[curLow] = array[curHigh];
                array[curHigh] = temp;
            }
        }

        // 此时curLow >= curHigh,把数组首元素与curHigh元素交换
        array[low] = array[curHigh];
        array[curHigh] = separateNum;

        // 将数组分两部分递归
        quickSort(array, low, curHigh-1);
        quickSort(array, curHigh+1, high);
    }
}

int main()
{
    const int size = 10;
    int arrayi[size] = {5, 2, 1, 5, 3, 4, 0, -1, 5, 1};
    char arrayc[size] = {'g', 's', 'd', 'j', 'k', 'n', 'e', 'r', 'a', 'b'};

    cout << "arrayi before sort : ";
    for(int i=0; i<size; ++i)
    {
        cout << arrayi[i] << ' ';
    }
    cout << endl;
    quickSort<int>(arrayi, 0, size-1);
    cout << "arrayi after sort : ";
    for(int i=0; i<size; ++i)
    {
        cout << arrayi[i] << ' ';
    }
    cout << endl;

    cout << "arrayc before sort : ";
    for(int i=0; i<size; ++i)
    {
        cout << arrayc[i] << ' ';
    }
    cout << endl;
    quickSort<char>(arrayc, 0, size-1);
    cout << "arrayc after sort : ";
    for(int i=0; i<size; ++i)
    {
        cout << arrayc[i] << ' ';
    }
    cout << endl;

    return 0;
}