【JavaDS】排序——快速排序_对用户输入的杂乱无序的数字序列按照由小到大的顺序排序。要求分别运用合并排序和

概念

1. 在序列中选择一个元素（如何选择并不重要，记为 pivot），通过遍历的方式，比较给定        元素和区间内其他元素的大小关系

2. 在遍历期间，通过算法的设计，将序列排成如下图序列

        注意：<= pivot 和 >= pivot 区间内顺序无法保证

                   pivot 也很大可能不在中间

3. 此时认为 pivot 就处于序列有序后其应该在的位置，最后对左右两个区间分别排序

排序过程中的小细节

1. 如果区间内元素个数 <= 1，则不用做任何处理，因为天然有序

2. 从区间中（这个区间不代表整个数组，需要用 [from, to] 来限定）中挑选一个 pivot ，方式      随意

3. 遍历区间，将每个元素都和 pivot 进行比较，并且进行必要的位置移动，使得遍历完成          后，满足上图所示区间

    把这个处理区间的过程称为 partition

    注意：partition 的过程只是快速排序中的一个小步骤，并非全部过程 

4.大区间处理完成后，继续对两个小区间按照同样的方法进行处理（算法可使用递归）

具体的 partition 的方法

partitionMethodA

从 array[left] 开始与 pivot 进行比较，当出现 array[left] > pivot 时，left++ 停止，array[right] 再与 pivot 比较，出现array[right] < pivot 时，right-- 停止，随后交换array[left] 和 array[right] ,重复此操作直到 [left, right) 区间内没有元素了（即 left ==right），最后再将 array[to] 和array[left](或 array[right] )的值交换（即将 pivot 的值放在序列中间），至此第一次 partition 完成

 partitionMethodB

最开始 to == right 

取 array[to] = pivot ,从array[left++] 开始依此与 pivot 进行比较，若遇到 > pivot 的元素，将array[left] 赋值给array[right] ,随后再从array[right--] 开始与 pivot 比较，若遇到 < pivot 的元素 ,将array[right] 赋值给 array[left] ,重复此步骤直至 left == right , 再将 pivot 的值赋给array[left],至此第一次 partition 完成

代码参考

private static int partitionMethodA(long[] array, int from, int to) {
        long pivot = array[to];
 
        int left = from;
        int right = to;
 
        while (left < right) {
 
            while (left < right && array[left] <= pivot) {
                left++;
            }
 
            while (left < right && array[right] >= pivot) {
                right--;
            }
 
            long t = array[left];
            array[left] = array[right];
            array[right] = t;
        }
 
        long t = array[to];
        array[to] = array[left];
        array[left] = t;
 
 
        return left;
    }
 
 
 
    private static int partitionMethodB(long[] array, int from, int to) {
        long pivot = array[to];
        int left = from;
        int right = to;
 
        while (left < right) {
            while (left < right && array[left] <= pivot) {
 
                right--;
            }
            array[right] = array[left];
 
            while (left < right && array[right] >= pivot) {
 
                left++;
            }
            array[left] = array[right];
        }
        array[left] = pivot;
        return left;
    }