数据结构学习笔记3.1--划分

划分是快速排序的根本机制，主要是把数组分为两组：小于关键字的数据项在一组，大于关键字的数据项在一组。

    /**
     * 划分数据
     * 
     * @param left 左边数据
     * @param right 右边数据
     * @param pivot 参照值
     * @return
     */
    public static int partitionIt(int left, int right, int pivot, int[] arr)
    {
        // 左边指针
        // 左边数据-1，为了后面执行++leftPrt操作时，数据能正确+1
        int leftPrt = left - 1;

        // 右边指针
        // 右边数据-1，为了后面执行--rightPrt操作时，数据能正确-1
        int rightPrt = right + 1;

        while (true)
        {
            // 左边数据比参照值的小，不做后续操作，循环
            while (leftPrt < right && arr[++leftPrt] < pivot);

            // 右边数据比参照值的大，不做后续操作，循环
            while (rightPrt > left && arr[--rightPrt] > pivot);

            if (leftPrt >= rightPrt)
            {
                break;
            }
            else
            {
                // 交左右两边的数据
                swap(leftPrt, rightPrt, arr);
            }
        }

        return leftPrt;
    }

    /**
     * 数据交换
     * 
     * @param index1 入参1
     * @param index2 入参2
     * @param arr 比较数组
     */
    public static void swap(int index1, int index2, int[] arr)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

算法中，我们可以这样理解：leftPrt是左边指针，rightPrt是右边指针，他们在数组下方移动（可以想象成两个人面对面行走）。

当leftPrt遇到比pivot（参照值）大时，跳出循环，此时leftPrt记录的是：大于pivot的数值所在的位置，即arr[leftPrt] > pivot；

当rightPrt遇到比pivot（参照值)小时，跳出循环，此时rightPrt记录的是：小于pivot的数值所在的位置，即arr[rightPrt] < pivot；

这时，找到的arr[leftPrt] ，arr[rightPrt] 都不在正确位置上，需要交换。

具体示例：

    /**
     * 测试函数
     * @param args
     */
    public static void main(String[] args)
    {
        int[] arr = { 90, 100, 20, 60, 80, 110, 120, 40, 10, 30, 50, 70 };
        partitionIt(0, arr.length - 1, 55, arr);

        for (int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");
        }
    }

代码执行过程中数组数据项：

可以看到leftPrt和rightPrt都在相互靠拢着移动，当leftPrt >= rightPrt时，循环结束。

划分的效率：运行时间为O(N)。