闲来无事，温习一下快速排序法

浏览数：27 / 时间：2015年06月08日

　　快速排序法，还是很常用的。不论是面试还是写代码。这里说一下怎么coding出快速排序法。至于什么复杂度之类的，请参考http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#C.

　　快速排序法的核心是分治法(Divide and conquer)，也就是把一个数组一分为二，二分为四....直到不能分了，也就完成排序了。所以快速排序法也就是怎么分的问题。怎么分？当然是按大小分了。所以快速排序法的升序步骤描述为：

选择一个基准元素
交换数组元素。把小于基准值的放到左边；大于基准值放右边；等于的放任意一边。保证基准元素就是分割线的位置。
将基准值左、右边的元素作为子数组（都不包括基准元素），重复上面两个步骤直到数组元素数量小于2

现在得出C++下代码：

#include <iostream>

using namespace std;

#define MAX_ARRAY 10

/**
 * @brief divide 分割数组
 * @param list
 * @param length
 * @return 分割位置
 * 以数组第一个元素为基准分割数组，
 * 左边为小于基准，右边大于基准
 * 以移动分割线的方法实现分割
 */
int divide( int *list,int length )
{
    int divide_line = 0;  /* 默认分割线 */
    int pivot = list[0];  /* 默认选择第一个作为基准 */

    swap ( list[0],list[length-1] );    /* 把基准放到最后，这样最后一个永远不会被交换 */

    for ( int i = 0;i < length;i ++ )
    {
        if ( list[i] < pivot )  /* 小于基准，要放到分割线左边 */
        {
            swap( list[i],list[divide_line] );    /* 交换 */

            /* 小于基准的元素增长，分割线右移,保证分割线(包括分割线)右边都不小于基准 */
            divide_line ++;
        }
    }

    swap ( list[divide_line],list[length-1] ); /* 把最后一个交换到分割线，保证分割线值为基准值 */

    return divide_line;
}

/**
 * @brief conquer 排序子数组
 * @param list
 * @param length
 * 将数组进行分割，并对子数组进行排序
 */
void conquer( int *list,int length )
{
    if ( length <= 1 )  //已分解为一个元素不再分解
        return;

    int divide_line = divide( list,length );    /* 得到分割线 */

    conquer( list,divide_line );  //排序左边的数组
    conquer( list+divide_line+1,length - divide_line - 1 );  //排序右边的数组,基准值不再需要排序
}

/**
 * @brief quick_sort 快速排序法
 * @param list
 * @param length
 * 快速排序法
 */
void quick_sort( int *list,int length )
{
    conquer( list,length );
}

int main()
{
    int list[MAX_ARRAY] = { 9,0,1,3,5,8,4,6,2,7 };

    quick_sort( list,MAX_ARRAY );

    for ( int i = 0;i < MAX_ARRAY;i ++ )
    {
        cout << list[i] << " ";
    }

    cout << endl;

    return 0;
}