在本文中，我們將討論快速排序算法?？焖倥判虻墓ぷ鞒绦蛞埠芎?jiǎn)單。

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

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

征服：遞歸地，使用快速排序?qū)蓚€(gè)子數(shù)組進(jìn)行排序。

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

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

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

選擇支點(diǎn)

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

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

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

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

算法

算法：

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

分區(qū)算法：

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

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)在，讓我們看看快速排序算法的工作原理。

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

讓數(shù)組的元素是 

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

由于樞軸在左側(cè)，因此算法從右側(cè)開(kāi)始并向左移動(dòng)。

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

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

因?yàn)椋琣[pivot] > a[right]，所以，算法將 a[pivot] 與 a[right] 交換，并且樞軸向右移動(dòng)，如

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

由于 a[pivot] > a[left]，所以算法向右移動(dòng)一個(gè)位置 

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

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

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

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

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

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

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

元素 24 右側(cè)的元素大于它，元素 24 左側(cè)的元素小于它。

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

快速排序復(fù)雜度

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

1.時(shí)間復(fù)雜度

最佳情況復(fù)雜性 -在快速排序中，當(dāng)樞軸元素是中間元素或靠近中間元素時(shí)會(huì)出現(xiàn)最佳情況。快速排序的最佳時(shí)間復(fù)雜度是O(n*logn)。

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

最壞情況復(fù)雜性 -在快速排序中，當(dāng)樞軸元素是最大或最小元素時(shí)會(huì)發(fā)生最壞情況。假設(shè)，如果樞軸元素始終是數(shù)組的最后一個(gè)元素，最壞的情況將發(fā)生在給定數(shù)組已經(jīng)按升序或降序排序的情況下?？焖倥判虻淖顗那闆r時(shí)間復(fù)雜度是O(n 2 )。

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

2. 空間復(fù)雜度

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

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

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

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

公共課 快速   
{  
    /* 將最后一個(gè)元素視為樞軸的函數(shù)，  
將樞軸放在其確切位置，并放置  
樞軸左側(cè)的較小元素和較大的元素  
樞軸右側(cè)的元素。*/  
int 分區(qū) ( int  a[],  int  start,  int  end)  
{  
    int  pivot = a[end]; // 樞軸元素  
    int  i = (開(kāi)始 -  1 );    
    for  ( int  j = start;j <= end -  1 ;j++)  
    {  
        // 如果當(dāng)前元素小于樞軸  
        如果 (a[j] < 樞軸)  
        {  
            我++； // 增加較小元素的索引  
            int  t = a[i];  
            a[i] = a[j];  
            a[j] = t;  
        }  
    }  
    整數(shù) t = a[i+ 1 ];  
    a[i+ 1 ] = a[結(jié)束];  
    a[結(jié)束] = t;  
    返回 (i +  1 );  
}    
/* 實(shí)現(xiàn)快速排序的函數(shù) */  
void  quick( int  a[],  int  start,  int  end)  /* a[] = 要排序的數(shù)組，start = 起始索引，end = 結(jié)束索引 */  
{  
    如果 （開(kāi)始<結(jié)束）  
    {  
        int  p = 分區(qū)（a，開(kāi)始，結(jié)束）；  //p是分區(qū)索引  
        快速（a，開(kāi)始，p -  1 ）；  
        快速（a，p +  1 ，結(jié)束）；  
    }  
}   
/* 打印數(shù)組的函數(shù) */  
void  printArr( int  a[],  int  n)  
{  
    詮釋 我;  
    對(duì)于 (i =  0 ; i < n; i++)  
        System.out.print(a[i] +  " " );  
}  
    公共靜態(tài)無(wú)效 主要（字符串[]參數(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í)行上述代碼后，輸出將是

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