快速排序（算法）

一、简介

        快速排序是一种高效的排序方法，且应用广泛，有时在面试中也会遇到。

二、排序思路

       总体思路：首先选择一个基准数，一般为第一个数，将所有比基准数小的数据放到其左右，比基准数大的数据放到其右边，然后使用递归的方式对两边的数据进行同样的处理，这样就可以达到排序的目的。

        原始数据：30、4、32、56、12、24

         基准数 base 为30，这里还需要借助两个整数指针，实现数据的移动。分别是p_start和p_end，p_start指向开头的数，这是是30，p_end指想最后的数据，这里是24。（p_start代表指针，指向某一个数，*p_start代表具体的数值）

        首先判断*p_start和*p_end的值，如果*p_start 大于 *p_end，需要将两个数字的位置调换。

if(*p_start > *p_end)
{
    tmp = *p_end;
    *p_end = *p_start;
    *p_start = tmp;
}

        此时数据变为：24、4、32、56、12、30

        判断指针的位置，确定基准数的位置，如果*p_start == base，说明*p_start < *p_end，需要p_end--，如果*p_start  != base，说明*p_start > *p_end,需要p_start++。

if(*p_start == base)
    p_end--;
else
    p_start++;

        此时p_strat指向 4 ，p_end指向 30。

        根据上方的原理一次类推，进行排序。

        24、4、32、56、12、30 ；

        *p_start = 4,*p_end = 30; *p_start < *p_end，无需交换，且p_start++；

        24、4、32、56、12、30；

        *p_start = 32,*p_end = 30; *p_start > *p_end，需要交换，且end--；

        24、4、30、56、12、32；

        *p_start = 30,*p_end = 12; *p_start > *p_end，需要交换，且p_start++；

        24、4、12、56、30、32；

         *p_start = 56,*p_end = 30; *p_start > *p_end，需要交换，且end--；

         24、4、12、30、56、32；

        此时 p_start  = p_end，两个指针重合，需要用到递归的方法，分别对指针两边的数据进行排序，从而达到排序的效果。

三、实现代码

void quick_sort(int* p_num,int size)
{
    int *p_start;
    int *p_end;
    int base,tmp;
    p_start = p_num;
    p_end = p_num + size -1; 

    if(size <= 0)
        return;

    while(p_end > p_start)
    {   
        if(*p_start > *p_end)
        {   
            tmp = *p_end;
            *p_end = *p_start;
            *p_start = tmp;
        }   

        if(*p_start == base)
            p_end--;
        else
            p_start++;
    }   
    quick_sort(p_num,p_start - p_num);
    quick_sort(p_start + 1,size - (p_start - p_num) - 1); 

}