三路快排

public static void sort(Comparable[] arr){

    int n = arr.length;
    sort(arr, 0, n-1);
}

// 递归使用快速排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r){

    // 对于小规模数组, 使用插入排序
    if( r - l <= 15 ){
        InsertionSort.sort(arr, l, r);
        return;
    }

    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr, l, (int)(Math.random()*(r-l+1)) + l );

    Comparable 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
    while( i < gt ){
        if( arr[i].compareTo(v) < 0 ){
            swap( arr, i, lt+1);
            i ++;
            lt ++;
        }
        else if( arr[i].compareTo(v) > 0 ){
            swap( arr, i, gt-1);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
    }

    swap( arr, l, lt );

    sort(arr, l, lt-1);
    sort(arr, gt, r);
}

总结: 归并和快速排序都采用了分治算法 分治算法:顾名思义,分而治之,就是将原问题,分割成同等结构的子问题,之后将子问题逐一解决后,原问题也就得到了解决。

results matching ""

    No results matching ""