入门算法：双路快速排序

上手难度：★★★☆

算法复杂度：O(nlogn)

之前介绍过的快速排序，当我们整个数组中包含有大量重复键值的时候，我们的Partition操作都有可能把整个数组分成极度不平衡的两部分（例如在满足左小右大的条件后，分成的两部分右边始终占据了大量数据）
导致快速排序退化成O(n^2)级别的算法

image.png

排序思想：

换一个思路Partition的程序
之前我们将小于v和大于v两部分全都放在了数组的一头
然后i从左到右，逐渐遍历完整个数组
现在将小于v和大于v两部分放在数组的两端
分别以i作为左边的索引，j作为右边的索引
i往右自增，j往左自减，当找到arr[i]>=v的值时，就和arr[j]<=v的值交换位置
直至把所有小于v的值交换到【l-i】这个范围，把所有大于v的值交换到【j~r】这个范围
直到i>j时就停止循环操作，此时i对应的就是右边第一个大于等于v的值，j对应的就是左边最后一个小于等于v的值
再交换l和j的值，j的位置就是v值了

代码实现：

public class QuickSort2 {

    private static Random random = new Random();

    private static int rand(int l, int r){
        return random.nextInt(r - l + 1);
    }

    /**
     * 交换数组中两个元素的位置
     */
    private static void swap(int[] arr, int x, int y){
        if(x < 0 || y < 0 || x > arr.length || y > arr.length){
            return;
        }
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    /**
     * 对arr[l...r]部分进行partition操作
     * 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
     */
    private static int partition2(int[] arr, int l, int r){
        swap(arr,  l, l + rand(l, r));

        int i = l + 1, j = r;

        int v = arr[l];

        while(true){

            while(i <= r && arr[i] < v){
                //当i小于等于右边界，并且对应值小于v时，继续向右移动i，目的是把小于v的值保留在左边，同时比较下一个值
                i++;
            }

            while(j >= l + 1 && arr[j] > v){
                //当j大于等于左边界，并且对应值大于v时，继续向左移动j，目的是把大于v的值保留在右边，同时比较下一个值
                j--;
            }

            if(i > j){
                break;
            }
            swap(arr, i, j);
            //当经过了上面两层循环，此时arr[i]就是大于v的值，arr[j]就是小于v的值，所以交换
            i++;
            j--;
        }
        //上面的循环走完，i停在了右边第一个>=v的位置，j停在了左边最后一个<=v的位置

        swap(arr, l , j);
        //交换l和j的值，这样在j左边的都是小于等于v的，在j右边的都是大于等于v的
        return j;
    }

    /**
     * 对ar[l...r]部分进行快速排序
     */
    public static void quickSort(int[] arr, int l, int r){
        if(l >= r){
            return;
        }

        int p = partition2(arr, l, r);
        //注意：这里返回p，之后，只是说满足arr[l+1...j] < v; arr[j+1...i) > v
        //并不是说p的左边一定有数组，或者p的右边一定有数组，也可能是空
        quickSort(arr, l, p - 1);
        //以p为中间点，再进行快速排序
        quickSort(arr, p + 1, r);
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        quickSort(arr, 0, arr.length - 1);

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

    }
}

优点

阻止了Quick Sort退化成O(n^2)级别的算法