快速排序算法思想及代码

快速排序算法原理：
1、对一个数组选定一个数作为标杆
2、把数组中比这个数“大”的数放到该数的左边
3、把数组中比这个数“小”的数放到该数的右边
4、根据标杆的位置，对标杆左右两边的数组进行调整

时间复杂度：
1、标杆数左右调整时间复杂度为O(n)
2、标杆的位置直接决定了快排的时间复杂度
    a、如果每次返回的标杆位置都位于数组中间，那么时间复杂度为O(n*logn)
    b、如果数组有序，那么标杆将是做个位置返回，此时的时间复杂度为O(n ^ 2)

同插入排序一样，使用函数指针隔离顺序变化

typedef int (*sort_comp)(void *, void *);

设定一个标杆，并进行调整（插入代码的控件太不好用），直接写吧。
static int sort_swap(int * a, int l, int r, sort_comp cmp)
{
    int sentry;//存放标杆的变量
    sentry = a[l];//把数组第一个数作为标杆
    while (l < r)
    {
        //右边开始，比标杆大则不调整
        while ((l < r) && (cmp(&sentry, &a[r]) < 0))
            r --;
        a[l] = a[r];//比标杆小则调整
        //左边开始，比标杆小则不调整
        while ((l < r) && (cmp(&sentry, &a[l]) > 0))
            l ++;
        a[r] = a[l];//比标杆大则调整
    }
    //标杆位置确定
    a[l] = sentry;
    return l;
}

根据标杆位置划定数组大小
static void _fast_sort(int * a, int l, int r, sort_comp cmp)
{
    int m;//标杆位置
    //只有一个数的数组就不调整了
    if (l >= r)
            return;
    m = sort_swap(a, l, r, cmp);//标杆位置左右已经符合右边比左边“大”
    //对标杆左边的数组进行调整
    _fast_sort(a, l, m - 1, cmp);
    //对标杆右边的数组进行调整
    _fast_sort(a,m + 1, r, cmp);
}

暴露一个排序接口给外部程序使用
int module_fast_sort(int * a, int len, sort_comp cmp)
{
    if (!a || !cmp)
        return 0;
    _fast_sort(a, 0, len - 1, cmp);
    return 1;
}