在本文中，我們將討論快速排序算法。快速排序的工作程序也很簡單。

排序是一種以系統(tǒng)方式排列項目的方式?？焖倥判蚴菑V泛使用的排序算法，它在平均情況下進行n log n比較，以對 n 個元素的數(shù)組進行排序。它是一種更快、更高效的排序算法。該算法遵循分而治之的方法。分而治之是一種將算法分解為子問題，然后解決子問題，并將結果組合在一起以解決原始問題的技術。

Divide：在 Divide 中，首先選擇一個樞軸元素。之后，將數(shù)組劃分或重新排列為兩個子數(shù)組，使得左子數(shù)組中的每個元素都小于或等于樞軸元素，而右子數(shù)組中的每個元素都大于樞軸元素。

征服：遞歸地，使用快速排序對兩個子數(shù)組進行排序。

組合：組合已經(jīng)排序的數(shù)組。

快速排序選擇一個元素作為樞軸，然后圍繞選擇的樞軸元素對給定數(shù)組進行分區(qū)。在快速排序中，一個大數(shù)組被分成兩個數(shù)組，其中一個保存小于指定值(樞軸)的值，另一個數(shù)組保存大于樞軸的值。

之后，左右子陣列也使用相同的方法進行分區(qū)。它將繼續(xù)，直到單個元素保留在子數(shù)組中。

選擇支點

選擇一個好的支點對于快速實現(xiàn)快速排序是必要的。但是，通常確定一個好的支點。選擇支點的一些方法如下 -

樞軸可以是隨機的，即從給定數(shù)組中選擇隨機樞軸。

Pivot 可以是給定數(shù)組最左邊元素的最右邊元素。

選擇中位數(shù)作為樞軸元素。

算法

算法：

QUICKSORT（數(shù)組 A，開始，結束）     
{  
如果 （開始 < 結束）      
  {  
  p = 分區(qū)（A，開始，結束）  
  QUICKSORT（A，開始，p -  1 ）    
  QUICKSORT (A, p +  1 , 結束)    
  }   
}  

分區(qū)算法：

分區(qū)算法將子數(shù)組重新排列在一個地方。

PARTITION (array A, start, end)     
{  
 pivot ? A[end]     
 i ? start-1     
 for j ? start to end -1 {  
 do if (A[j] < pivot) {    
 then i ? i + 1     
 swap A[i] with A[j]   
  }}   
 swap A[i+1] with A[end]     
 return i+1  
}  

快速排序算法的工作

現(xiàn)在，讓我們看看快速排序算法的工作原理。

為了理解快速排序的工作原理，讓我們看一個未排序的數(shù)組。它將使概念更加清晰和易于理解。

讓數(shù)組的元素是 

在給定的數(shù)組中，我們將最左邊的元素視為樞軸。因此，在這種情況下，a[left] = 24、a[right] = 27 和 a[pivot] = 24。

由于樞軸在左側，因此算法從右側開始并向左移動。

現(xiàn)在，a[pivot] < a[right]，所以算法向左移動一個位置，即 

現(xiàn)在，a[left] = 24，a[right] = 19，a[pivot] = 24。

因為，a[pivot] > a[right]，所以，算法將 a[pivot] 與 a[right] 交換，并且樞軸向右移動，如

現(xiàn)在，a[left] = 19、a[right] = 24 和 a[pivot] = 24。由于樞軸在右側，所以算法從左開始并向右移動。

由于 a[pivot] > a[left]，所以算法向右移動一個位置 

現(xiàn)在，a[left] = 9，a[right] = 24，a[pivot] = 24。由于 a[pivot] > a[left]，所以算法向右移動一個位置 

現(xiàn)在，a[left] = 29、a[right] = 24 和 a[pivot] = 24。由于 a[pivot] < a[left]，所以，交換 a[pivot] 和 a[left]，現(xiàn)在進行樞軸在左邊，即

由于樞軸在左側，因此算法從右側開始，然后向左移動?，F(xiàn)在，a[left] = 24，a[right] = 29，a[pivot] = 24。由于 a[pivot] < a[right]，所以算法向左移動一個位置，如

現(xiàn)在，a[pivot] = 24、a[left] = 24 和 a[right] = 14。由于 a[pivot] > a[right]，所以，交換 a[pivot] 和 a[right]，現(xiàn)在進行 pivot在右邊，即

現(xiàn)在，a[pivot] = 24，a[left] = 14，a[right] = 24。pivot 在右邊，所以算法從左開始向右移動。

現(xiàn)在，a[pivot] = 24、a[left] = 24 和 a[right] = 24。因此，pivot、left 和 right 指向同一個元素。它代表程序的終止。

作為樞軸元件的元件24被放置在其確切位置。

元素 24 右側的元素大于它，元素 24 左側的元素小于它。

現(xiàn)在，以類似的方式，快速排序算法分別應用于左右子數(shù)組。排序完成后，數(shù)組將是 

快速排序復雜度

現(xiàn)在，讓我們看看快速排序在最佳情況、平均情況和最壞情況下的時間復雜度。我們還將看到快速排序的空間復雜度。

1.時間復雜度

最佳情況復雜性 -在快速排序中，當樞軸元素是中間元素或靠近中間元素時會出現(xiàn)最佳情況?？焖倥判虻淖罴褧r間復雜度是O(n*logn)。

平均案例復雜度 -當數(shù)組元素處于混亂的順序，沒有正確升序和降序時，就會發(fā)生這種情況?？焖倥判虻钠骄咐龝r間復雜度為O(n*logn)。

最壞情況復雜性 -在快速排序中，當樞軸元素是最大或最小元素時會發(fā)生最壞情況。假設，如果樞軸元素始終是數(shù)組的最后一個元素，最壞的情況將發(fā)生在給定數(shù)組已經(jīng)按升序或降序排序的情況下。快速排序的最壞情況時間復雜度是O(n 2 )。

盡管快速排序的最壞情況復雜度比合并排序和堆排序等其他排序算法要高，但在實踐中它仍然更快?？焖倥判蛑凶顗牡那闆r很少發(fā)生，因為通過更改樞軸的選擇，它可以以不同的方式實現(xiàn)。通過選擇正確的樞軸元素可以避免快速排序中的最壞情況。

2. 空間復雜度

快速排序的空間復雜度為 O(n*logn)。

快速排序的實現(xiàn)

現(xiàn)在，讓我們看看不同編程語言的快速排序程序。

程序：編寫程序以在 Java 中實現(xiàn)快速排序。

公共課 快速   
{  
    /* 將最后一個元素視為樞軸的函數(shù)，  
將樞軸放在其確切位置，并放置  
樞軸左側的較小元素和較大的元素  
樞軸右側的元素。*/  
int 分區(qū) ( int  a[],  int  start,  int  end)  
{  
    int  pivot = a[end]; // 樞軸元素  
    int  i = (開始 -  1 );    
    for  ( int  j = start;j <= end -  1 ;j++)  
    {  
        // 如果當前元素小于樞軸  
        如果 (a[j] < 樞軸)  
        {  
            我++； // 增加較小元素的索引  
            int  t = a[i];  
            a[i] = a[j];  
            a[j] = t;  
        }  
    }  
    整數(shù) t = a[i+ 1 ];  
    a[i+ 1 ] = a[結束];  
    a[結束] = t;  
    返回 (i +  1 );  
}    
/* 實現(xiàn)快速排序的函數(shù) */  
void  quick( int  a[],  int  start,  int  end)  /* a[] = 要排序的數(shù)組，start = 起始索引，end = 結束索引 */  
{  
    如果 （開始<結束）  
    {  
        int  p = 分區(qū)（a，開始，結束）；  //p是分區(qū)索引  
        快速（a，開始，p -  1 ）；  
        快速（a，p +  1 ，結束）；  
    }  
}   
/* 打印數(shù)組的函數(shù) */  
void  printArr( int  a[],  int  n)  
{  
    詮釋 我;  
    對于 (i =  0 ; i < n; i++)  
        System.out.print(a[i] +  " " );  
}  
    公共靜態(tài)無效 主要（字符串[]參數(shù)）{    
    int  a[] = {  13 ,  18 ,  27 ,  2 ,  19 ,  25  };  
    int  n = a.length;  
    System.out.println( "\n排序前的數(shù)組元素為-" );  
    快速 q1 =  new  Quick();  
    q1.printArr(a, n);  
    q1.quick(a,  0 , n -  1 );  
    System.out.println( "\n排序后的數(shù)組元素為-" );  
    q1.printArr(a, n);  
    System.out.println();  
    }  
}  

輸出

執(zhí)行上述代碼后，輸出將是

以上就是關于“快速排序算法詳解”的介紹，算法還有很多，本站的數(shù)據(jù)結構和算法教程中找到合適的案例，加強我們對各種排序算法的理解。