快速排序

描述

采用分治的思想(Divide and conquer)
分解：把数组划分为两个子数组，找一个基准数x，使左边元素都小于x，右边元素都大于x
解决：通过递归调用快速排序对数组A[a:i]和A[i+1:b]排序，基准数不用排

下面试快速排序的伪代码：

伪代码

image.png

python描述

def partition(array, a, b):
    if len(array) > 0:
        x = array[a]
        i = a
        for j in range(a+1, b):
            if array[j] <= x:
                i += 1
                array[i], array[j] = array[j], array[i]
        array[a], array[i] = array[i], array[a]
        print(array)
    return i

def quick_sort(array, a, b):
    if a < b:
        i = partition(array, a, b)
        quick_sort(array, a, i)
        quick_sort(array, i+1,b)

java描述

public class Quick {
    
    public static void sort(Comparable[] a){
        sort(a, 0, a.length-1);
    }
    
    private static void sort(Comparable[] a, int start, int end){
        if(start > end){
            return;
        }
        
        int j = partition(a, start, end);
        // 将左半部分排序
        sort(a, start, j-1);
        // 将右半部分排序
        sort(a, j+1, end);
    }
    
    private static int partition(Comparable[] a, int start, int end){
        Comparable flag = a[end];
        int i = start;
        
        for(int j = start; j < end; j++){
            if(less(a[j], flag)){
                exch(a, i, j);
                i++;
            }
        }
        exch(a, i, end);
        return i;
    }
    
    public static void main(String[] args) {
        Integer[] a = {2, 3, 1, 3, 4, 8, 6, 10};
        sort(a);
        assert isSorted(a);
        show(a);
    }
    
    public static boolean less(Comparable V , Comparable W){
        return V.compareTo(W) < 0;
    }
    
    public static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ");   
        }
        System.out.println();
    }
    
    // 测试数组元素是否有序
    public static boolean isSorted(Comparable[] a){
        for (int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
}

算法分析

快速排序的最坏时间复杂度是O(n²)，但是只有在已经排好序的情况下时间复杂度是O(n²)，平均时间复杂度或者说期望运行时间比较可观，为O(nlgn)

随机优化

在选择主元素（基准数）时，可以随机选取，因为主元素时随机选取的，我们期望在
在平均的情况下，对数组的划分是比较均衡的
代码下次补上