【算】快速排序

godiscoder 發(fā)布于2019-08-15 14:51 / 2898人閱讀

摘要：分治快速排序以下簡(jiǎn)稱(chēng)快排的核心思想是分治法。第二個(gè)元素大于，放于右側(cè)第三個(gè)元素小于，放于左側(cè)以此類(lèi)推，最后一個(gè)元素放置完畢后是這樣的重復(fù)。此時(shí)從左到右讀出圖中曾作為基準(zhǔn)值的元素菱形，我們發(fā)現(xiàn)已經(jīng)排序好了。

分治

快速排序（以下簡(jiǎn)稱(chēng)“快排”）的核心思想是分治法。可以說(shuō)，分治提供了另一種解決問(wèn)題的思路。舉個(gè)例子來(lái)進(jìn)行說(shuō)明，抓穩(wěn)扶好，直接開(kāi)車(chē)了……

舉例

現(xiàn)有一個(gè)集合{4,8,2,5,7,-1,3}，我們將對(duì)它進(jìn)行從小到大排序：

1.選取第一個(gè)元素4作為基準(zhǔn)值，后面的元素逐個(gè)和這個(gè)基準(zhǔn)值比較大小

顯然，要么大于，要么小于（暫不考慮相等的情況）。

2.按比較大小結(jié)果進(jìn)行安置：大于基準(zhǔn)值的元素，置于它的左側(cè)；小于基準(zhǔn)值的元素，置于它的右側(cè)（如果有相等情況，左右隨意）

為好理解，畫(huà)出了數(shù)軸，將"基準(zhǔn)值4"作為中軸線。第二個(gè)元素8大于4，放于右側(cè)；第三個(gè)元素2小于4，放于左側(cè)……以此類(lèi)推，最后一個(gè)元素放置完畢后是這樣的

3.“重復(fù)”。先拋開(kāi)右側(cè)的big集合，專(zhuān)注于左側(cè)集合{2,-1,3}。此時(shí)，我們把它當(dāng)作source，重復(fù)第一步的操作。

如此重復(fù)下去，直到只剩下一個(gè)元素的情況。

此時(shí)從左到右讀出圖中曾作為基準(zhǔn)值的元素（菱形）——-1,2,3,4，我們發(fā)現(xiàn)已經(jīng)排序好了。最后給出完整的操作示意圖：

每次根據(jù)條件劃分成兩部分，劃分后每部分分別治理，即分治。

遞歸

上面的例子中，第三步叫“重復(fù)”其實(shí)并不準(zhǔn)確，真正的名字是遞歸。

每個(gè)遞歸函數(shù)都有兩部分：

基線條件：函數(shù)不再調(diào)用自己，即退出無(wú)限循環(huán)調(diào)用的條件

遞歸條件：調(diào)用自己，且通過(guò)一次次調(diào)用會(huì)逐步靠攏基線條件

拿上一篇文章（【算】選擇排序和二分查找）里聊過(guò)的二分查找舉例：

/**
 * 二分查找，遞歸版
 * @param target
 * @param source
 * @return
 */
public static int doFind(int target,List source){
    if(CollectionUtils.isEmpty(source)){
        throw new RuntimeException("集合為空");
    }
    int halfIndex = source.size()/2;
    int halfElement = source.get(halfIndex).getVal();
    if(target==halfElement){    //基線條件：如果目標(biāo)target和中間數(shù)相等，bingo！找到了，返回索引
        return source.get(halfIndex).getIndex();
    }else if(source.size()==1){ //另一個(gè)基線條件：就剩下最后一個(gè)元素了，仍然與目標(biāo)target不符，則返回“目標(biāo)不存在”
        throw new RuntimeException("目標(biāo)不存在");
    }else{  //遞歸條件：選取符合條件的那一半集合，遞歸調(diào)用自己
        if (target < halfElement) {
            List tempSource = source.subList(0, halfIndex);
            return doFind(target, tempSource);
        } else {
            List tempSource = source.subList(halfIndex, source.size());
            return doFind(target, tempSource);
        }
    }
}

快排

掌握了遞歸和分治思想后，快速排序就只剩下編碼部分了：

/**
 * 快排
 * @param source
 * @return
 */
public static List doOrder(List source){
    if(source.size()<=1){   //基線條件
        return source;
    }
    int temp = source.get(0);
    List lowElements = new LinkedList<>();
    List highElements = new LinkedList<>();
    for(int i=1,len=source.size();i res = new LinkedList<>(lowElements);
    res.add(temp);
    res.addAll(highElements);
    return res;
}

快排的平均時(shí)間復(fù)雜度為O(n log n)