摘要：快排可以說是一道必知的常見面試題，同時也有多種實現(xiàn)方式。之所以使用隨機快速排序而不是普通的快排。其中交換數(shù)組元素位置，打印元素的方法我就沒貼了，代碼太長你們也不方便看。

快排可以說是一道必知的常見面試題，同時也有多種實現(xiàn)方式。在這篇文章中，我使用的是隨機三路快排。

之所以使用隨機快速排序而不是普通的快排。是因為前者可以使得數(shù)列有序的概率降低，從而使隨機快速排序平均速度是比快速排序要快的。具體的兩者的性能差別可以看下這篇文章：

https://blog.csdn.net/haelang...

talk id cheap，show the code。一共 20+ 行代碼，每行代碼都有注釋。其中交換數(shù)組元素位置，打印元素的方法我就沒貼了，代碼太長你們也不方便看。

PS：代碼下面有執(zhí)行流程圖，結(jié)合代碼來看比較容易理解。

public static void main(String[] args) {                                             
     // 測試數(shù)據(jù)                              
     int[] arr = new int[]{5, 3, 6, 4}; 
     // 執(zhí)行快排
     quickSort(arr, 0, arr.length - 1);         
     // 打印數(shù)組元素              
     printArray(arr);                           
 }  
 
private static void quickSort(int[] arr, int l, int r) {               
     if (l < r) {                                                       
         // 隨機取需要排序的數(shù)組中的一個元素和數(shù)組的最后一個元素交換，作為劃分值                          
         swap(arr, l + (int) (Math.random() * (r - l + 1)), r);       
         // 得到數(shù)組元素中等于劃分值的區(qū)域                                             
         int[] part = partition(arr, l, r);                             
         // 小于等于劃分值的區(qū)域                                                  
         quickSort(arr, l, part[0] - 1);                                
         // 大于劃分值的區(qū)域                                                    
         quickSort(arr, part[1] + 1, r);                                
     }                                                                  
 }   

private static int[] partition(int[] arr, int l, int r) {                                                                   
    // 初始化小于等于劃分值區(qū)域的當(dāng)前下標(biāo)，默認(rèn)是數(shù)組第一個元素的前一個位置                                                                                   
    int less = l - 1;                                                                                                       
    // 初始化大于劃分值區(qū)域的當(dāng)前下標(biāo)，默認(rèn)是數(shù)組最后一個元素的位置，同時也是劃分值的位置，但該值并不屬于大于劃分值的區(qū)域，所以要在最后進(jìn)行移動                                                 
    int more = r;                                                                                                           
    // 當(dāng)前下標(biāo)小于大于劃分值區(qū)域的下標(biāo)時                                                                                                    
    while (l < more) {                                                                                                      
        // 當(dāng)前值比劃分值小，當(dāng)前值和小于等于劃分值區(qū)域的右邊第一個值進(jìn)行交換，小于等于劃分值區(qū)域右移1個下標(biāo)，當(dāng)前下標(biāo)+1                                                         
        if (arr[l] < arr[r]) {                                                                                              
            swap(arr, l++, ++less);                                                                                         
            // 當(dāng)前值比劃分值大，當(dāng)前值和大于劃分值區(qū)域的左邊第一個值進(jìn)行交換，大于劃分值的區(qū)域左移1個下標(biāo)                                                               
        } else if (arr[l] > arr[r]) {                                                                                       
            swap(arr, l, --more);                                                                                           
            // 當(dāng)前值等于劃分值，當(dāng)前下標(biāo)+1                                                                                              
        } else {      
            // 當(dāng)前下標(biāo)+1                                                                                          
            l++;                                                                                                            
        }                                                                                                                   
    }                                                                                                                       
    // 將劃分值和大于劃分值區(qū)域中，最接近劃分值區(qū)域的元素交換。至此完成所有值的區(qū)域劃分                                                                             
    swap(arr, more, r);                                                                                                     
    // 返回等于劃分值的區(qū)域                                                                                                           
    return new int[]{less + 1, more};                                                                                       
} 

下面我會畫個流程圖幫大家理解一下，測試數(shù)據(jù)和代碼一樣。

假設(shè)代碼執(zhí)行完 13 行后，測試數(shù)據(jù)的順序依舊不變，即為 {5,3,6,4}。

接下來在執(zhí)行 partition() 方法的過程中，數(shù)組元素的情況如下圖所示（靈魂寫手求輕噴）

好了，以上就是本文的全部內(nèi)容，我們下篇文章再見，捂臉逃~

PS：本文原創(chuàng)發(fā)布于微信公眾號「不只Java」，后臺回復(fù)「Java」，送你 13 本 Java 經(jīng)典電子書。公眾號專注分享 Java 干貨、讀書筆記、成長思考