[[385051]]

本文轉(zhuǎn)載自微信公眾號(hào)「貝塔學(xué)JAVA」，作者Silently9527。轉(zhuǎn)載本文請(qǐng)聯(lián)系貝塔學(xué)JAVA公眾號(hào)。

本文已被Github倉(cāng)庫(kù)收錄 https://github.com/silently9527/JavaCore

程序員常用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin

完全開(kāi)源的淘客項(xiàng)目：https://github.com/silently9527/mall-coupons-server

前言

快速排序可以說(shuō)是使用最廣的排序算法了，主要的特點(diǎn)是基于原地排序(不需要使用輔助數(shù)組，節(jié)省空間);其實(shí)對(duì)于長(zhǎng)度為N的數(shù)組使用快速排序時(shí)間復(fù)雜度為 NlogN;在前幾篇也一起討論了其他的排序算法，都沒(méi)能夠把這兩個(gè)特點(diǎn)結(jié)合起來(lái)。

快速排序思路

快速排序也是一種分治的排序算法，把數(shù)組劃分為兩個(gè)子數(shù)組，然后遞歸對(duì)子數(shù)組進(jìn)行排序，最終保證整個(gè)數(shù)組有序。

算法思路：

1. 隨機(jī)選擇一個(gè)切分元素，通常選擇的是數(shù)組的第一個(gè)元素
2. 從數(shù)組的左邊開(kāi)始掃描找出大于等于切分元素的值，從數(shù)組的右邊開(kāi)始掃描找出小于等于切分元素的值，交換這兩個(gè)值
3. 循環(huán)這個(gè)過(guò)程直到左右兩個(gè)指針相遇，這樣就排定了一個(gè)元素，保證了切分元素左邊的值都是小于它的值，右邊的元素都是大于它的值
4. 遞歸這個(gè)過(guò)程，最終保證整個(gè)數(shù)組有序

算法實(shí)現(xiàn)

根據(jù)快速排序算法的思路，我們可以寫(xiě)出第一版實(shí)現(xiàn)：

public class QuickSort implements SortTemplate { 
    @Override 
    public void sort(Comparable[] array) { 
        quickSort(array, 0, array.length - 1); 
    } 
 
    private void quickSort(Comparable[] array, int lo, int hi) { 
        if (lo >= hi) { 
            return; 
        } 
        int partition = partition(array, lo, hi); 
        quickSort(array, lo, partition - 1); 
        quickSort(array, partition + 1, hi); 
    } 
 
    private int partition(Comparable[] array, int lo, int hi) { 
        int i = lo, j = hi + 1; 
        Comparable el = array[lo]; 
        while (true) { 
            while (less(array[++i], el)) { 
                if (i == hi) { 
                    break; 
                } 
            } 
            while (less(el, array[--j])) { 
                if (j == lo) { 
                    break; 
                } 
            } 
            if (i >= j) { 
                break; 
            } 
            exch(array, i, j); 
        } 
        exch(array, lo, j); 
        return j; 
    } 
} 

這段代碼是實(shí)現(xiàn)快速排序的常規(guī)實(shí)現(xiàn)，考慮最糟糕的情況，假如需要排序的數(shù)組是已經(jīng)有序的[1,2,3,4,5,6,7,8]，執(zhí)行快速排序的過(guò)程如圖：

對(duì)一個(gè)長(zhǎng)度為N的數(shù)組，最糟糕的情況下需要遞歸N-1次，所以時(shí)間復(fù)雜度是O(n2)，為了避免這種情況出現(xiàn)，我們來(lái)看下算法如何改進(jìn)

算法改進(jìn)

• 保證隨機(jī)性 為了避免最糟糕的情況出現(xiàn)，有兩個(gè)辦法，第一是在排序數(shù)組之前先隨機(jī)打亂數(shù)組;第二是在partition方法中隨機(jī)取切分元素，而不是固定取第一個(gè)，簡(jiǎn)單實(shí)現(xiàn)：

private int partition(Comparable[] array, int lo, int hi) { 
    int i = lo, j = hi + 1; 
    int random = new Random().nextInt(hi - lo) + lo; 
    exch(array, lo, random); 
    Comparable el = array[lo]; 
    while (true) { 
        while (less(array[++i], el)) { 
            if (i == hi) { 
                break; 
            } 
        } 
        while (less(el, array[--j])) { 
            if (j == lo) { 
                break; 
            } 
        } 
        if (i >= j) { 
            break; 
        } 
        exch(array, i, j); 
    } 
    exch(array, lo, j); 
    return j; 
} 

• 切換到插入排序 這點(diǎn)和歸并排序一樣，對(duì)于小數(shù)組的排序直接切換成插入排序

private void quickSort(Comparable[] array, int lo, int hi) { 
    if (lo >= hi) { 
        return; 
    } 
     
    if (hi - lo < 5) {  //測(cè)試，小于5就切換到插入排序 
        insertionSort(array, lo, hi); 
        return; 
    } 
 
    int partition = partition(array, lo, hi); 
    quickSort(array, lo, partition - 1); 
    quickSort(array, partition + 1, hi); 
} 
 
//插入排序 
private void insertionSort(Comparable[] array, int lo, int hi) { 
    for (int i = lo; i <= hi; i++) { 
        for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { 
            exch(array, j, j - 1); 
        } 
    } 
} 

三向切分 當(dāng)我們需要排序的數(shù)組中出現(xiàn)了大量的重復(fù)元素，我們實(shí)現(xiàn)的快速排序在遞歸的時(shí)候會(huì)遇到許多全部重復(fù)的子數(shù)組，我們的算法依然會(huì)對(duì)其進(jìn)行切分，這里有很大的提升空間。

思路就是先隨意選擇一個(gè)切分元素(el)，然后把數(shù)組切換成大于、等于、小于三個(gè)部分，一次遞歸可以排定所有等于切分元素的值;維護(hù)一個(gè)指針lt、gt，使得a[lo..lt-1]都小于切分元素，a[gt+1..hi]都大于切分元素;

• 初始化變量：lt=lo, i=lo+1, gt=hi
• if a[i] < el ; 交換a[i]與a[lt], i++, lt++
• if a[i] > el ; 交換a[gt]與a[i], gt--
• a[i] == el; i++

代碼實(shí)現(xiàn)：

public class Quick3waySort implements SortTemplate { 
    @Override 
    public void sort(Comparable[] array) { 
        quickSort(array, 0, array.length - 1); 
    } 
 
    @SuppressWarnings("unchecked") 
    private void quickSort(Comparable[] array, int lo, int hi) { 
        if (lo >= hi) { 
            return; 
        } 
        int lt = lo, i = lo + 1, gt = hi; 
        Comparable el = array[lo]; 
        while (i <= gt) { 
            int tmp = el.compareTo(array[i]); 
            if (tmp > 0) { 
                exch(array, lt++, i++); 
            } else if (tmp < 0) { 
                exch(array, i, gt--); 
            } else { 
                i++; 
            } 
        } 
        quickSort(array, lo, lt - 1); 
        quickSort(array, gt + 1, hi); 
    } 
}