基本思路

快速排序的基本思想是头尾两个指针不断靠近，他们经过的值与基准值比较，符合条件则交换两指针内容，然后递归调用由基准值分成的两个区间。

优化

若基准值选到靠近等差序列端点的值，那么算法的效率将很低，一种优化方法是每次递归时取头中尾三个值的中间值作为基准值。

void swap(int *nums, int i, int j) 
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

int partition(int *nums, int low, int high)
{
    int mid = low + ((high-low) >> 1);
    if (nums[low] > nums[high]) swap(nums,low,high);
    if (nums[mid] > nums[high]) swap(nums,mid,high);//前两句保证尾部为最大值
    if (nums[mid] > nums[low]) swap(nums,mid,low);//保证头部值为中间值
    int pivot = nums[low];
    int start = low;
    while(low<high)
    {
        while(low<high && nums[high]>=pivot) high--;//尾指针先接近，确保头指针指向的值小于基准值
        while(low<high && nums[low]<=pivot) low++;
        if(low>=high) break;
        swap(nums, low, high);
    }
    swap(nums, low, start);//基准值归位

    return low;
}

void quickSort(int *nums, int low, int high)
{
    int index;
    if(low >= high)
        return;
    index = partition(nums, low, high);
    quickSort(nums, low, index-1);
    quickSort(nums, index+1, high);
}