排序––快速排序（二）

根据排序––快速排序（一）的描述，现准备写一个快速排序的主体框架：

1、首先需要设置一个枢轴元素即setPivot(int i)；

2、然后需要与枢轴元素进行比较即int comparePivot(int j); 

3、最后是关键步骤，将比枢轴元素大的排在右边，小的排在左边，然后对左右两边的数重复123的步骤，先进行以下几种情况的讨论：

    （1）假设给定序列7、6、5、4、3、2、1，并选择4为枢轴，则示例代码如下：

sort(int from, int to) {

        if(from == to) {
            return;
        }
        int right = to;
        int left = from;
        while (true) {
            while (comparePivot(right) > 0) {
                right--;
            }

            while (comparePivot(left) < 0) {
                left++;
            }
            if (left == right) {
                break;
            }
            swap(left, right);
        }
        sort(from, left - 1);
        sort(right + 1, to);
    }

     验证一下：7和1进行交换，序列变成1、6、5、4、3、2、7；left=0;right=6;

                      6和2进行交换，序列变成1、2、5、4、3、6、7；left=1;right=5;

                      5和3进行交换，序列变成1、2、3、4、5、6、7；left=2;right=4;

                      left=3;right=3;退出循环

                      然后分别调用sort(0,2),sort(4,6)，对于sort(0,2)的排序过程如下：

                       假设选取2为枢轴，由于原始序列已经有序，right=1;left=1;退出循环。 最后的两个递归是sort(0,0)以及sort(2,2),这两个递归会由于from==to条件直接退出。

                      sort(4,6)也是类似的情况。

                    最后整个序列就是有序序列，由此看来该程序貌似正确，但是此情况比较特殊，为了能适应一般的情况，还需改进。其实正确的快速排序代码量很少，但是要把各种情况分析到位，写一个正确的快速排序代码个人认为起码没有其它排序算法那么简单。下篇再继续分析排序过程中可能会出现的各种情况。