入门算法：三路快速排序

上手难度：★★★★

算法复杂度：O(nlogn)

排序思想：

预先设定三个空间
l为最左边的索引
初始值lt=l, gt=r+1, i = l + 1
arr[l+1~lt) 存放的是小于v的值
arr[l+1 ~ i)存放的是等于v的值
arr[gt~r]存放的是大于v的值
初始的时候这三个区间都为空
进入while(i < gt)的循环
当arr[i]<v时，将i和lt+1的值交换位置，同时i和lt向右移动，i移动是为了比较下一个值，lt移动是因为左边的区间多了一个值
当arr[i]>v时，将i和gt-1的值交换位置，gt向左移动，i不变，因为交换来的值还未判断，所以i不动
当arr[i]=v时，不做交换操作，i继续向右移动
循环完成后，lt到gt之间的值就不需要再排序了，然后将继续切分小于v的区间和大于v的区间即可

代码实现：

public class QuickSort3 {

    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;
    }

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

        swap(arr,  l, l + rand(l, r));

        int v = arr[l];

        int lt = l;
        // 索引对应arr[l+1...lt) < v
        int gt = r + 1;
        // 索引对应arr[gt...r] > v
        int i = l + 1;
        // 索引对应arr[lt+1...i) = v 在初始情况下，这些区间都是空的，符合逻辑，首先假设有这样的数组空间了，
        //随着lt、gt、i的变动以及交换位置，就可以把这三个区间确定下来

        //当i移动到从右往左数 最后一个大于v的值的位置时，就不用循环了
        while(i < gt){
            if(arr[i] < v){
                //当i索引的值小于v，就将其与lt+1的值调换位置，同时i继续往右移动，lt因为多了一个值，也要往右移动
                //lt+1的值之前已经判断过了，因此不需要再处理，直接将i移动
                swap(arr, i, lt + 1);
                i++;
                lt++;
            }else if(arr[i] > v){
                //当i索引的值大于v，就将其与gt-1的值调换位置，将大于v的值放到gt区间
                //然后继续判断调换过来的值，因此i不用移动，gt因为多了一个值，所以要往左移动
                swap(arr, i, gt - 1);
                gt--;
            }else{
                i++;
            }
        }
        //l对应的值就是v，lt对应的是最后一个小于v的值，交换后，v就放在了合适的位置，即v的左边小于v，右边大于等于v
        swap(arr, l, lt);

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

    }
}

优点：

不需要对大量等于v的元素重复操作，在包含大量相同元素时，三路排序最有效率
另外快速排序在 取出数组中第n大的元素这类问题效率很高，算法复杂度为O(n)，因为快速排序的过程每一次都是找到一个标定点，然后将标定点挪到数组中合适的位置，这个合适的位置就是数组排好序后最终所处的位置，所以第n大元素，就是第n个位置的元素