4.快速排序（Quick sort）

题目

使用快速排序法将{1, 9, 8, 3, 5} （或其他乱序的数组）按升序排序得到 {1, 3, 5, 8, 9}。

解题思路

快速排序的核心思想：先随机找到一个支点(pivot)，找到这个支点在数组中真正的index(排序好后的index),在寻找index的同时把所有比pivot value小的元素放左边,大于等于pivot的元素放右边; 然后以支点为切口将数组切开成左右两部分(不包含支点)，再从这两部分各随机选中一个支点找到其在数组中真正的位置，循环往复直至无法再切割为止。

寻找pivot index的过程
1.随机确定一个pivot
2.将pivot放到最右边
3.根据随机选中的pivotIndex分区，定义左右挡板(指针):i, j向中间遍历比较ele与pivot ele的大小,比pivot小的元素放左边，大于等于pivot的元素放右边；
4.最后i就是我们要找的pivotIndex，将最右边的pivot与i互换位置即可

while(i<=j){
if(arr[i]<pivot){
    i++;
}else(arr[j]>=pivot){
    j--;
}else{  //arr[i]>=pivot&&arr[j]<pivot
    swap(arr, i, j);
    i++;
    j--;
}
}
 swap(arr, i, pivot);

图示：

2.png

Code

public class QuickSortTest {

    @Test
    public void test() throws Exception {
        int[] arr = new int[]{1, 9, 8, 5, 3};
        arr = quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private Random random = new Random();

    //time complexity
    //O(nlgn) --> O(n^2)
    //space complexity
    //O(lgn) --> O(n);
    public int[] quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr;
        }
        int left = 0;
        int right = arr.length - 1;
        int pivotIndex = partition(arr, left, right);//找出第一层的pivot index
        //分组各自递归寻找pivot index
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
        return arr;
    }

    private void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;//base case
        int pivotIndex = partition(arr, left, right);//找出第一层的pivot index
        //分组各自递归寻找pivot index
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }

    //分区(随机选一个pivot并找到它在数组中正确的index)
    private int partition(int[] arr, int left, int right) {
        //1.防止over flow 2.防止遇到排好序的数组时产生worse case(最差情况)
        int pivotIndex = left + random.nextInt(right - left + 1);
        int pivot = arr[pivotIndex];
        swap2(arr, pivotIndex, right);//将pivot放到最右边，便于其他元素做大小比较
        pivotIndex = right;
        int l = left, r = right - 1;
        while (l <= r) {
            if (arr[l] < pivot) {
                l++;
            } else if (arr[r] >= pivot) {
                r--;
            } else {//arr[l]>=pivot&&arr[r]<pivot
                swap2(arr, l, r);
                l++;
                r--;
            }
        }
        swap2(arr, l, pivotIndex);//将pivot换到正确的位置
        return l;
    }


    //交换数组的元素 实现2，在函数调用次数巨大的情况下可以提高一些效率
    private void swap2(int[] arr, int index1, int index2) {
        if (index1 == index2) return;
        arr[index1] = arr[index1] + arr[index2];
        arr[index2] = arr[index1] - arr[index2];
        arr[index1] = arr[index1] - arr[index2];
    }

    //交换数组的元素
    private void swap1(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }


}

时空复杂度分析

时间复杂度
partition()这个函数在递归的每一层循环次数相加复杂度是N，每一层都是N那么意味着我们只要算出递归树的层数*N就可以得出quick sort算法的时间复杂度，分两种情况：

worst case：最差情况，当给定一个排序好的数组{1，2，3，4，5，6}当pivot选到6的时候，算法的递归树是这样的：

3.png

总共是N层，所以当给定一个排序好的数组并且pivot选最小或最大的元素时会遇到worst case，最差时间复杂度是O(n^2);

average case：平均时间复杂度，当给定一个乱序的数组{4,2,0,7,3}当pivot选3的时候，算法的递归树是这样的：

4.png

所以平均时间复杂度是O(nlgn)。

空间复杂度：
空间复杂度跟递归层数有关，最差情况下是O(nlgn),一般情况是O(lgN)。

merge sort与quick sort的区别

时空复杂度区别:
归并排序和快排的平均时间复杂度时一样的都是O(nlgn),而quick sort的空间复杂度O(lgn)优于merge sort的空间复杂度O(n),因为merge sort多创建了一个helper数组。
重要区别：
两个都是递归算法，不同点在于merge sort是先递归分裂再do something(merge)，而quick sort是先do something(partition)在递归分裂。