入门算法：快速排序

上手难度：★★★☆

算法复杂度：O(nlogn)~O(n^2)

test.gif

排序思想：

取最左边索引p对应的值为参考值，循环遍历数组，将数组剩下来的值分为两部分，左边是小于p的值，右边是大于p的两部分，然后返回p索引，再对这分好的两部分继续分下去，直至分到不能分为止，这样数组中每个位置均满足左边是小于右边的，也就完成了排序

代码实现：

public class QuickSort {

    //交换数组中两个元素的位置
    public 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]
    public static int partition(int[] arr, int l, int r){
        
        int v = arr[l];//记住此时最左边的值
        int p = l;//最开始p的位置就是最左边

        for(int i = l; i <= r; i++){
            if(arr[i] < v){
                swap(arr, p+1, i);//将第一个大于v的元素和正在考察的元素进行了位置的交换，把小的换到前面来了
                p++;//通过p++移动索引，因为调换之后p自增之前就是小于arr[p]的值了
            }
        }

        swap(arr, p, l);//这样p的位置放的就是v，而l放置的就是原来p位置上小于v的元素
        //因为经过上面的循环，p被换过小于v的值，所以将v和p位置对应的值调换，就形成了p的左边都是小于arr[p]的值，p的右边都是大于arr[p]的值

        return p;//虽然返回了满足性质的p，但是左右两个区间并不是从小到大排序的，没关系，后续还会继续按这个操作划分
        //通过p分割成两个区间后，再对这两个区间进行分割，返回子区间的p，直至到最后传进的参数l=r为止
    }

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

        int p = partition(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(' ');
        }
    }
}

缺点：

平衡度比归并排序要差，并且我们不能完全保证分割后树的高度就是logn，当完全有序的情况，整颗递归树的高度为n

归并排序
快速排序

最差的情况

最差的情况
所以它的算法复杂度在O(nlogn)~O(n^2)之间

优化方法：

1、随机选择一个元素作为标定元素，此时快速排序的时间复杂度期望值是O(nlogn)
退化成n^2级别的算法概率是非常低的，第一次就选择到最小的元素，概率是1/n，第二次选择到最小的元素，概率是1/(n-1)
对标定元素的索引取值进行随机取值，在partition最开始加入下面的代码

swap(arr[l], arr[rand()%(r-l+1)+l]);//随意调换下位置，避免出现最差的情况

2、双路快速排序法
3、三路快速排序法（后续补充）