快速排序

• 基于分治思想：先选取枢轴位置，枢轴位置的数记为key。然后将小于key的数都排在枢轴位置前面，将大于key的数都排在枢轴位置后面。

代码版本一：《剑指offer》

//选取中枢位置函数
int Partition(int data[], int length, int start, int end)
{
    if(data  == NULL || length <= 0 || end >= length || start < 0)
        return -1;
    // 随机选取index更好，此处直接省略为中间位置
    int index = (start + end) / 2;
    
    // 将key暂存于末尾
    swap(&data[index], &data[end]);
    
    // small是一个索引位置，索引小于等于small的数小于等于选中的key（即data[end]）
    int small = start - 1;
    for(int i = start; i < end; i++)
    {
        if(data[i] < data[end])
        {
            ++small;
            if(small != i)
                swap(&data[i], &data[small]);
        }
    }
    ++small;
    swap(&data[small], &data[end]);
    return small;
}

//快排主函数
void QuickSort(int data[], int length, int start, int end)
{
    if(start == end) // 只有一个数，有序，直接返回
        return;
    int index = Partition(data, length, start, end);
    if(index > start)
        QuickSort(data, length, start, index -1);
    if(index < end)
        QuickSort(data, length, index + 1, end);
}