排序——快速排序

一，快速排序的主体递归部分字正腔圆，通常随便写一下也不会写出什么大的问题的。

主要要注意的或者说要记住的就是:

1)low < high判定。

2)mid-1和mid+1，即partition之后mid已经在位置了。

如下所示：

void quick_sort(int a[], int low, int high)
{
    if (low < high)
    {
        int mid = partition(a,low,high);

        quick_sort(a,low,mid-1);
        quick_sort(a,mid+1,high);
    }
}

二，重要的是partition部分，即让选定的元素到位。

其中需要注意的点是：（即partition的步骤）

1）选定元素（直接选a[low]）；

2）交替扫描的次序：注意先从高端向低端扫描，而后从低端向高端扫描；

（当然可以其他方法，需要修改调整代码）

3）i < j的限定，防止i与j的交错出现异常错误。

如下所示：

int partition(int a[], int low, int high)
{
    int cur = a[low];
    int i = low;
    int j = high;

    while (i < j)
    {
        while(a[j] >= cur && i < j)
        {
            j--;
        }
        swap(a[i], a[j]);
        // cur跑到右边了

        while(a[i] <= cur && i < j)
        {
            i++;
        }
        swap(a[i], a[j]);
        // cur跑到左边了
    }
    return i;
}

跟踪选定的元素cur可以发现，其最后的位置落在i=j上。

注意到最终i是等于j的，i=j后还做了一次原位swap操作，即swap(a[i],a[i])。

三，进一步的，partition可以不使用swap，只使用赋值。

优化调整的代码如下：

int partition(int a[], int low, int high)
{
    int cur = a[low];
    int i = low;
    int j = high;

    while(i < j)
    {
        while(a[j] >= cur && i < j)
        {
            j--;
        }
        a[i] = a[j];
        while (a[i] <= cur && i < j)
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = cur;
    return i;
}

四，基本上到这里就行了，不必再进一步的优化了。（枢轴元素的随机化、相邻元素的逆序交换等什么什么的）