譯者 | 朱先忠

審校 | 重樓

摘要：本文將詳細介紹一種新穎高效的順序劃分算法——循環(huán)劃分算法，它能夠?qū)ζ胀愋椭禂?shù)據(jù)進行最小次數(shù)的重新排列。

1.導(dǎo)言

順序劃分是計算機編程中一種基本且常用的算法。給定一個數(shù)字序列“A”和一個稱為基準(zhǔn)值的值“p”，劃分算法的目的是以這種方式重新排列“A”中的數(shù)字，使所有小于“p”的數(shù)字排在第一位，然后是其余的數(shù)字。

按基準(zhǔn)值“p=20”劃分前后的序列示例。應(yīng)用算法后，所有小于20的值（淺綠色）顯示在其他值之前（黃色）。

劃分算法有不同的應(yīng)用，但最受歡迎的應(yīng)用包括：

• 快速排序（QuickSort）——一種劃分算法，在給定數(shù)組的不同子數(shù)組上通過遞歸多次調(diào)用，直到最終完成排序。
• 找到給定序列的中值——利用劃分來有效地縮小搜索范圍，并最終在預(yù)期的線性時間內(nèi)找到中值。

對序列進行排序是在大量數(shù)據(jù)上實現(xiàn)更快導(dǎo)航的重要步驟。在兩種常見的搜索算法中——線性搜索和二分查找——后者只有在數(shù)組中的數(shù)據(jù)被排序時才能使用。找到中位數(shù)或k階統(tǒng)計量對于理解給定未排序數(shù)據(jù)中的值分布至關(guān)重要。

目前已經(jīng)存在不同的劃分算法（也稱為劃分方案），但最著名的要算是“Lomuto方案”和“Hoare方案”。Lomuto方案通常直觀上更容易理解，而Hoare方案在給定數(shù)組內(nèi)的重排次數(shù)較少，這就是它在實踐中通常更受歡迎的原因。

在本文中，我要推薦的是一種新的劃分方案，稱為“循環(huán)劃分”，它類似于Hoare方案，但數(shù)組內(nèi)的重新排列（值賦值）要少1.5倍。因此，正如稍后將顯示的那樣，值賦值的數(shù)量幾乎等于最初“不在原位”的值的數(shù)量，并且應(yīng)該以某種方式移動。這一事實讓我認為這個新的劃分方案幾乎是最優(yōu)的。

接下來的內(nèi)容按以下方式組織：

• 在第2節(jié)中，我們將回顧什么是就地劃分（一種屬性，它使得劃分操作不那么繁雜）
• 在第3節(jié)中，我們將回顧廣泛使用的Hoare劃分方案
• 在第4節(jié)中，我將介紹“循環(huán)賦值”，我們將了解為什么序列的某些重排可能需要比同一序列的其他重排更多的值賦值
• 第5節(jié)將利用“賦值循環(huán)”的一些性質(zhì)，推導(dǎo)出新的“循環(huán)劃分”方案，作為Hoare方案的優(yōu)化變體
• 最后，第6節(jié)將對小數(shù)據(jù)類型和大數(shù)據(jù)類型的數(shù)組進行Hoare方案和循環(huán)劃分的實驗比較。

請注意，GitHub上已經(jīng)提供了基于C++語言的循環(huán)劃分的實現(xiàn)，以及它與當(dāng)前標(biāo)準(zhǔn)Hoare方案的基準(zhǔn)測試，詳見本文末尾的引用文獻。

2.原地順序劃分回顧

如果輸入和輸出序列位于計算機內(nèi)存中的2個不同數(shù)組中，則對序列進行劃分將不是一項艱巨的任務(wù)。如果情況是這樣的話，那么其中一種方法可能是：

• 計算“A”中有多少值小于“p”（這將給出輸出序列左半部分的最終長度）
• 從左到右掃描輸入數(shù)組“A”，并將每個當(dāng)前值“A[i]”附加到左側(cè)或右側(cè)，具體取決于它是否小于“p”。

以下是運行此類算法的幾個狀態(tài)：

在第一階段，我們計算出只有7個值小于“p=20”（淺綠色的值），因此我們準(zhǔn)備從索引7開始將較大的值寫入輸出序列。

在第二階段掃描輸入序列的5個值之后，我們將其中的3個附加到輸出序列的左側(cè)部分，另兩個在其右側(cè)。

繼續(xù)第二階段，我們現(xiàn)在從輸入序列中掃描了9個值，將其中5個放置在輸出序列的左側(cè)，將另外4個放置在其右側(cè)。

算法完成（現(xiàn)在，輸出序列的兩個部分都已正確填充到末尾）

注意，這里保留了左邊部分或右邊部分中數(shù)值的相對順序（根據(jù)它們最初在輸入數(shù)組中的寫入方式）。

當(dāng)然，還有其他更簡短的解決方案，比如代碼中只有一個循環(huán)的解決方案。

現(xiàn)在，當(dāng)我們不想使用任何額外的內(nèi)存時，困難就來了。因此，只需在唯一的數(shù)組中移動值，輸入序列就會被轉(zhuǎn)換為劃分后的輸出序列。順便說一句，這種不使用額外內(nèi)存的算法稱為就地算法。

用相同的基準(zhǔn)值“p=20”對相同的輸入序列“A”進行劃分

這里顯示的值順序?qū)?yīng)于序列的輸入狀態(tài)，每個值都顯示箭頭——如果應(yīng)該將該值移動到某處，以便對整個序列進行劃分。

在介紹我的劃分方案之前，讓我們首先來回顧一下現(xiàn)有的和常用的就地劃分解決方案。

3.目前使用的劃分方案

在觀察了各種編程語言的標(biāo)準(zhǔn)庫中排序的一些實現(xiàn)后，看起來使用最廣泛的劃分算法是Hoare方案。我發(fā)現(xiàn)它被用于例如：

• C++STL中的“std::sort()”實現(xiàn)
• JDK for Java中用于原始數(shù)據(jù)類型的“Arrays.sort()”實現(xiàn)

在基于Hoare方案的劃分中，我們從兩端向彼此同時掃描序列，在左側(cè)部分搜索大于或等于'p'的a[i]值，在右側(cè)部分搜索小于'p'的a[j]值。一旦找到，我們就知道這兩個值A(chǔ)[i]和A[j]都屬于“不在它們的正確位置”（記住，劃分序列應(yīng)該先有小于'p'的值，然后才有大于或等于'p'所有其他值），所以我們只需要交換A[i]與A[j]。交換后，我們繼續(xù)以同樣的方式，同時掃描索引為i和j的數(shù)組“A”，直到它們相等。一旦完成，劃分就完成了。

讓我們在另一個例子中觀察Hoare方案：

長度為'N'的輸入序列“A”，應(yīng)按基準(zhǔn)值“p=20”進行劃分

索引i從0開始向上掃描，索引j從“N-1”開始向下掃描。

當(dāng)增加索引i時，我們會遇到值“A[2]=31”，它大于“p”。然后，在減小索引j之后，我們遇到另一個值“A[10]=16”，它小于'p'。這兩個將被交換。

在交換“A[2]”和“A[10]”之后，我們繼續(xù)從2增加i，從10減少j。索引i將在大于'p'的值“A[4]=28”時停止，索引j將在小于'p]的值“A[9]=5”時停止。這兩個也將被交換。

算法以同樣的方式繼續(xù)，數(shù)字“A[5]=48”和“A[7]=3”也將被交換。

之后，索引“i”和“j”將彼此相等。至此，劃分算法完成。

如果用Hoare方案編寫劃分的偽代碼，我們將得到以下內(nèi)容：

// 對序列A[0..N)進行劃分，使用基準(zhǔn)值 'p' 
// 根據(jù)Hoare方案，并返回結(jié)果右邊部分第一個值的索引。
function partition_hoare( A[0..N) : Array of Integers, p: Integer ) : Integer
 i := 0
 j := N-1
 while true
 // 根據(jù)需要向左移動索引“i”
 while i < j and A[i] < p
 i := i+1
 // 根據(jù)需要向右移動索引“j”
 while i < j and A[j] >= p
 j := j-1
 // Check for completion
 if i >= j
 if i == j and A[i] < p
 return i+1 // "A[i]" 指向左邊部分
 else
 return i // "A[i]"指向右邊部分 
//交換"A[i]"和"A[j]"
 tmp := A[i]
 A[i] := A[j]
 A[j] := tmp
 //'i'和'j'各自加1
 i := i+1
 j := j-1

在第5行和第6行中，我們?yōu)?次掃描設(shè)置了開始索引。

第8-10行從左側(cè)搜索這樣一個值，該值在劃分后應(yīng)屬于右側(cè)。

同樣，第11-13行從右側(cè)搜索這樣一個值，它應(yīng)該屬于左側(cè)。

第15-19行檢查掃描是否完成。一旦索引'i'和'j'相遇，就有兩種情況：“A[i]”屬于左部分或右部分。根據(jù)這一點，我們返回“i”或“i+1”，因為函數(shù)的返回值應(yīng)該是右側(cè)部分的開始索引。

接下來，如果掃描尚未完成，第20-23行會交換那些不在正確位置的2個值。

最后，第24-26行各自把這兩個索引加1，以便不重新檢查已經(jīng)交換的值。

該算法的時間復(fù)雜度為O（N），無論兩次掃描在哪里相遇，因為它們總是一起掃描N個值。

這里有一個重要的注意事項，如果數(shù)組“A”的'L'值“不在它們的位置”，并且應(yīng)該被交換，那么按照Hoare方案，我們將進行“3*L/2”賦值，因為交換2個值需要3個賦值：

交換2個變量“a”和“b”的值，需要在“tmp”變量的幫助下進行3次賦值。

這些任務(wù)是：

tmp := a

a := b

b := tmp

需要強調(diào)一下，“L”總是偶數(shù)。這是因為對于最初位于左側(cè)區(qū)域的每個值“A[i]>=p”，都有另一個值“A[j]<p”最初位于右側(cè)區(qū)域，這些值正在被交換。因此，每次交換都會重新排列2個這樣的值，Hoare方案中的所有重新排列都是通過交換完成的。這就是為什么“L”——要重新排列的值的總數(shù)——總是偶數(shù)。

4.循環(huán)賦值

本節(jié)內(nèi)容可能看起來與本文主題有所偏離，但實際上并非如此，因為在優(yōu)化Hoare劃分方案時，我們需要在下一節(jié)中了解循環(huán)賦值的知識。

假設(shè)我們想以某種方式重新排列給定序列“A”中的值的順序。這不一定是劃分，而是任何形式的重新排列。讓我來證明一下，一些重排列需要比其他一些排列更多的賦值操作。

情形1：序列的循環(huán)左移

如果我們想將序列“A”循環(huán)左移1個位置，應(yīng)該完成多少個賦值操作？

長度為N=12的序列“A”的循環(huán)左移示例

我們看到所需的賦值操作數(shù)量為N+1=13，因為我們需要：

1）將“A[0]”存儲在臨時變量“tmp”中，然后

2）“N-1”次將右相鄰值賦值給當(dāng)前值，最后

3）將“tmp”賦值給序列“A[N-1]”的最后一個值。

要做到這一點，所需的操作是：

tmp := A[0]
A[0] := A[1]
A[1] := A[2]
...
A[9] := A[10]
A[10] := A[11]
A[11] := tmp

……這導(dǎo)致了13次賦值操作。

情形2：循環(huán)左移3個位置

在下一個例子中，我們?nèi)匀幌雽ν恍蛄羞M行循環(huán)左移，但現(xiàn)在向左移動3個位置：

序列“A”的循環(huán)左移3的示例，長度N=12

我們看到值A(chǔ)[0]、A[3]、A[6]和A[9]正在相互交換（藍色箭頭）

以及值A(chǔ)[1]、A[4]、A[7]和A[10]（粉紅色箭頭）

并且由于值A(chǔ)[2]、A[5]、A[8]和A[11]僅在彼此之間交換（黃色箭頭）。

“tmp”變量被賦值和讀取了3次。

這里我們有3個獨立的賦值鏈/循環(huán)，每個長度為4。

為了在A[0]、A[3]、A[6]和A[9]之間正確交換值，需要采取以下行動：

tmp := A[0]
A[0] := A[3]
A[3] := A[6]
A[6] := A[9]
A[9] := tmp

……這里進行了5次賦值。同樣，在組（A[1]，A[4]，A[7]，A[10]）和（A[2]，A[5]，A[8]，A[11]）內(nèi)交換值將需要分別進行5次賦值。將所有這些加在一起，得到了將序列“A”循環(huán)左移3所需的5*3=15個賦值，其中N=12個值。

情形3：顛倒順序

當(dāng)反轉(zhuǎn)長度為“N”的序列“A”時，執(zhí)行的操作是：

• 將其第一個值與最后一個值交換，然后
• 將第二個值與右側(cè)的第二個進行交換，
• 將第三個值與右側(cè)的第三個進行交換，
• ……等等。

反轉(zhuǎn)數(shù)組“A”的示例，其中N=12個值

我們看到成對的值（A[0]，A[11]），（A[1]，A[10]），（A[2]，A[9]）等正在相互獨立地交換。變量“tmp”被賦值和讀取6次。

由于每個交換都需要3次賦值，而對于反轉(zhuǎn)整個序列“A”，我們需要進行N/2交換，因此賦值的總數(shù)為：

3*N/2=3*12/2=3*6=18

與“A”相反的賦值的確切順序是：

tmp := A[0] // 循環(huán)1
A[0] := A[11]
A[11] := tmp
tmp := A[1] // 循環(huán)2
A[1] := A[10]
A[10] := tmp

...

tmp := A[5] // 循環(huán)6
A[5] := A[6]
A[6] := tmp

小結(jié)

我們已經(jīng)看到，重新排列相同序列“A”的值可能需要不同數(shù)量的賦值，具體取決于重新排列值的確切方式。

在所提供的3個示例中，序列的長度始終為N=12，但所需分配的數(shù)量不同：

更確切地說，賦值次數(shù)等于N+C，其中“C”是重排過程中產(chǎn)生的循環(huán)次數(shù)。在這里，我所說的“循環(huán)”是指“a”的變量子集，其值在彼此之間旋轉(zhuǎn)。

在我們的例子1（左移1）中，我們只有C=1個賦值循環(huán)，“A”的所有變量都參與了這個周期。這就是為什么賦值總數(shù)是：

N+C=12+1=13。

在情形2（左移3）中，我們有C=3個賦值循環(huán)，其中：

變量內(nèi)的第一個循環(huán)（A[0]、A[3]、A[6]、A[9]）

第二個循環(huán)應(yīng)用于變量（A[1]、A[4]、A[7]、A[10]）

第三個循環(huán)應(yīng)用于變量（A[2]，A[5]，A[8]，A[11]）。

這就是為什么賦值總數(shù)是：

N+C=12+3=15。

在我們的情形3（反轉(zhuǎn)）中，我們有?N/2?=12/2=6個周期。這些都是最短的可能循環(huán)，并應(yīng)用于配對（A[0]，A[11]），（A[1]，A[10]），…等等。這就是為什么賦值的總數(shù)是：

N+C=12+6=18。

當(dāng)然，在所提供的示例中，賦值數(shù)量的絕對差異非常小，在編寫高性能代碼時不會起任何作用。但這是因為我們考慮了一個長度為“N=12”的非常短的數(shù)組。對于較長的數(shù)組，賦值數(shù)量的差異將與N成比例增長。

在結(jié)束本節(jié)時，讓我們記住，重新排列序列所需的賦值數(shù)量會隨著這種重新排列所引入的循環(huán)數(shù)量而增長。如果我們想更快地重新排列，我們應(yīng)該嘗試通過這樣一個方案來實現(xiàn)，該方案具有盡可能少的賦值循環(huán)。

5.優(yōu)化Hoare劃分方案

現(xiàn)在，讓我們再次觀察Hoare劃分方案，這次要注意它引入了多少個賦值循環(huán)。

假設(shè)我們有一個長度為N的相同數(shù)組“A”，以及一個必須根據(jù)其進行劃分的基準(zhǔn)值“p”。另外，讓我們假設(shè)數(shù)組中有'L'值，應(yīng)該以某種方式重新排列，以便將“A”帶入劃分狀態(tài)。事實證明，Hoare劃分方案以最慢的方式重新排列這些“L”值，因為它引入了最大可能的賦值循環(huán)數(shù)，每個循環(huán)僅由2個值組成。

給定基準(zhǔn)值“p=20”，應(yīng)重新排列的“L=8”值是朝箭頭方向（或離開箭頭方向）。

Hoare劃分方案引入了“L/2=4”個賦值循環(huán)，每個循環(huán)只作用于2個值。

在長度為2的循環(huán)中移動2個值，本質(zhì)上就是交換它們，需要3次賦值。因此，Hoare劃分方案的值賦值總數(shù)為“3*L/2”。

我將要描述的優(yōu)化背后的想法來自這樣一個事實，即在對序列進行劃分后，我們通常對值“a[I]<p”的相對順序不感興趣，這些值應(yīng)該在劃分序列的左側(cè)結(jié)束，我們也不關(guān)心值的相對順序，這些值應(yīng)在右側(cè)結(jié)束。我們唯一感興趣的是，所有小于“p”的值都排在其他值之前。這一事實允許我們改變Hoare方案中的賦值循環(huán)，并只產(chǎn)生一個賦值循環(huán)，其中包含所有的“L”值，這些值應(yīng)該以某種方式重新排列。

讓我先借助下圖描述一下更改后的劃分方案：

更改后的劃分方案，應(yīng)用于相同的序列“A”

由于基準(zhǔn)值“p=20”沒有改變，因此應(yīng)重新排列的“L=8”值也相同。

所有箭頭代表新方案中唯一的賦值循環(huán)。

在將所有“L”值移動到它上面之后，我們將得到一個替代的劃分序列。

那么，我們在這里干什么呢？

• 與原始Hoare方案一樣，首先我們從左側(cè)掃描并找到這樣的值“A[i]>=p”，它應(yīng)該位于右側(cè)。但是，我們沒有用其他值交換它，而是記住它：“tmp:=A[i]”。
• 接下來，我們從右側(cè)掃描，找到這樣的值“A[j]<p”，它應(yīng)該位于左側(cè)。我們只需執(zhí)行賦值“A[i]:=A[j]”，而不會丟失“A[i]”的值，因為它已經(jīng)存儲在“tmp”中。
• 接下來，我們從左側(cè)繼續(xù)掃描，找到這樣的值“A[i]>=p”，它也應(yīng)該轉(zhuǎn)到右側(cè)。因此，我們進行賦值“A[j]：=A[i]”，而不會丟失值“A[j]”，因為它已經(jīng)被賦值給了'i'的前一個位置。
• 這種模式繼續(xù)下去，一旦索引i和j相遇，仍然需要將大于'p'的值放置在“A[j]”中，我們只需執(zhí)行“A[j]：=tmp”，因為最初變量“tmp”保存了從左起的第一個值，大于'p’。劃分完成。

正如我們所看到的，這里我們只有一個遍歷所有“L”值的賦值循環(huán)，為了正確地重新排列它們，與Hoare方案的“3*L/2”賦值相比，只需要“L+1”值賦值。

我更喜歡將這種新的劃分方案稱為“循環(huán)劃分”，因為所有應(yīng)該以某種方式重新排列的“L”值現(xiàn)在都位于一個賦值循環(huán)中。

下面給出的是循環(huán)劃分算法的偽代碼。與Hoare方案的偽代碼相比，這些變化微不足道，但現(xiàn)在我們將少做1.5倍的任務(wù)。

// 通過“循環(huán)劃分”方案將序列A[0..N）與樞軸值'p'進行劃分，
//并返回結(jié)果右側(cè)部分的第一個值的索引。
function partition_cyclic( A[0..N) : Array of Integers, p: Integer ) : Integer
 i := 0
 j := N-1
 // 找到左邊第一個不在其位置的值
 while i < N and A[i] < p
 i := i+1
 if i == N
 return N // 所有N值都移到左側(cè)
 //下面開始循環(huán)賦值
 tmp := A[i] // 唯一一次寫向變量'tmp'
 while true
 // 根據(jù)需要向右移動索引“j”
 while i < j and A[j] >= p
 j := j-1
 if i == j // 檢查掃描是否完成
 break
 //循環(huán)中的下一個賦值
 A[i] := A[j]
 i := i+1
 //根據(jù)需要向左移動索引“i”
 while i < j and A[i] < p
 i := i+1
 if i == j // 檢查掃描是否完成
 break
 // 循環(huán)中的下一個賦值
 A[j] := A[i]
 j := j-1
 // 掃描已經(jīng)完成
 A[j] := tmp // 唯一一次讀變量'tmp'
 return j

上面代碼中，第5行和第6行設(shè)置了兩次掃描的開始索引（'i'從左到右，'j'從右到左）。

第7-9行從左側(cè)搜索這樣的值“a[i]”，該值應(yīng)位于右側(cè)。如果事實證明沒有這樣的值，并且所有N個項目都屬于左側(cè)部分，則第10行和第11行會報告這一點并完成算法。

否則，如果找到了這樣的值，在第13行，我們會將其記在“tmp”變量中，從而在索引“i”處打開一個空位，用于在那里放置另一個值。

第15-19行從右側(cè)搜索這樣的值“a[j]”，該值應(yīng)移動到左側(cè)。一旦找到，第20-22行將其放入索引“i”處的空位中，之后索引“j”處的位置變?yōu)榭眨⒌却硪粋€值。

同樣，第23-27行從左側(cè)搜索這樣的值“a[i]”，該值應(yīng)移動到右側(cè)。一旦找到，第28-30行將其放入索引“j”處的空位中，之后索引“i”處的位置再次變空，并等待另一個值。

這種模式在算法的主循環(huán)中繼續(xù)，在第14-30行。

一旦索引'i'和'j'相遇，我們就會在那里有一個空位，第31行和第32行將'tmp'變量中最初記憶的值賦值給那里，因此索引'j'成為第一個保存屬于右側(cè)部分的值的索引。

最后一行返回該索引。

這樣我們就可以在循環(huán)體中一起編寫循環(huán)的2個賦值，因為正如第3節(jié)所證明的那樣，“L”總是偶數(shù)。

該算法的時間復(fù)雜度也是O（N），因為我們?nèi)匀粡膬啥藪呙栊蛄小Ｋ粫p少1.5倍的值賦值，因此加速僅反映在常數(shù)因子中。

注意：GitHub網(wǎng)站上提供了C++語言中循環(huán)劃分的實現(xiàn)，且在本文末尾引文中也有提供。

我還想證明，無論我們使用什么劃分方案，Hoare方案中的值“L”都不能降低。假設(shè)劃分后，左部分的長度為“l(fā)eft _n”，右部分的長度也為“right _n”。現(xiàn)在，如果查看原始未劃分?jǐn)?shù)組的左對齊“l(fā)eft_n”長區(qū)域，我們會在那里找到一些“t1”值，這些值不在它們的最終位置。因此，這些值大于或等于“p”，無論如何都應(yīng)該移動到右側(cè)。

劃分前后順序的圖示

左側(cè)部分的長度為“l(fā)eft_n=7”，右側(cè)部分的長度是“right_n=5”。

在未劃分序列的前7個值中，有“t1=3”

它們大于“p=20”（黃色），應(yīng)該以某種方式移動到右側(cè)。

在未劃分序列的最后5個值中，有“t2=3”

它們小于“p”（淺綠色的），應(yīng)該以某種方式移動到左側(cè)。

同樣，如果查看原始未劃分?jǐn)?shù)組的右側(cè)的“right_n”長度范圍，我們會在那里找到一些't2'值，這些值也不在它們的最終位置。這些值小于'p'，應(yīng)該移到左邊。我們不能從左向右移動小于“t1”的值，也不能從右向左移動小于“t2”的值。

在Hoare劃分方案中，“t1”和“t2”值是相互交換的值。所以我們有：

t1 = t2 = L/2,

或者：

t1 + t2 = L.

這意味著，“L”實際上是應(yīng)該以某種方式重新排列的最小數(shù)量的值，以便對序列進行劃分。循環(huán)劃分算法僅通過“L+1”賦值重新排列它們。這就是我允許自己將這種新的劃分方案稱為“近乎最優(yōu)”的原因。

6.實驗結(jié)果

已經(jīng)證明，新的劃分方案執(zhí)行的值賦值更少，因此我們可以預(yù)期它運行得更快。然而，在發(fā)布算法之前，我也想以實驗的方式收集結(jié)果。

我比較了使用Hoare方案和循環(huán)劃分進行劃分時的運行時間。所有實驗都是在隨機亂序的數(shù)組中進行的。

實驗中，使用的不同的參數(shù)有：

• N——數(shù)組的長度，
• “l(fā)eft_part_percent”——劃分后左部分長度的百分比（N時）
• 在原始數(shù)據(jù)類型變量（32位整數(shù)）的數(shù)組上運行，與在某種大型對象的數(shù)組（256個16位整數(shù)的長靜態(tài)數(shù)組）上運行相比。我想澄清為什么我發(fā)現(xiàn)有必要在原始數(shù)據(jù)類型的數(shù)組和大型對象的數(shù)組上運行劃分。在這里，我所說的“大對象”是指與原始數(shù)據(jù)類型相比占用更多內(nèi)存的值。在對原始數(shù)據(jù)類型進行劃分時，將一個變量分配給另一個變量的速度將與這兩種算法中使用的幾乎所有其他指令一樣快（例如遞增索引或檢查循環(huán)條件）。同時，在對大型對象進行劃分時，與其他使用的指令相比，將一個這樣的對象分配給另一個對象將花費更多的時間，而此時我們有興趣盡可能減少值賦值的總數(shù)。
  我將在本節(jié)稍后解釋為什么我決定用不同的“l(fā)eft_part_percent”值進行不同的實驗。
  實驗是在以下系統(tǒng)下使用Google Benchmark性能測試工具進行的：
• CPU：英特爾酷睿i7–11800H@2.30GHz
• 內(nèi)存：16.0 GB
• 操作系統(tǒng)：Windows 11家庭版，64位
• 編譯器：MSVC 2022（/O2/Ob2/MD/GR/Gd）

對原始數(shù)據(jù)類型的數(shù)組進行劃分

以下是對原始數(shù)據(jù)類型（32位整數(shù)）的數(shù)組運行劃分算法的結(jié)果：

在長度為N=10000的32位整數(shù)數(shù)組上劃分算法的運行時間

藍色條對應(yīng)于Hoare方案的劃分，而紅色條對應(yīng)于循環(huán)劃分算法。

劃分算法針對5種不同的情況運行，基于“l(fā)eft_part_percent”——劃分后出現(xiàn)的數(shù)組左半部分的百分比（N）。時間以納秒為單位。

我們觀察到，“l(fā)eft_part_percent”的值與兩種算法運行時間的相對差異之間沒有明顯的相關(guān)性。這種行為是意料之中的。

對“大型對象”數(shù)組進行劃分

以下是在所謂的“大對象”數(shù)組上運行2個劃分算法的結(jié)果，每個對象都是一個256長度的16位隨機整數(shù)靜態(tài)數(shù)組。

大對象數(shù)組上劃分算法的運行時間（256個隨機16位整數(shù)的長靜態(tài)數(shù)組），長度N=10000

其中，藍色條對應(yīng)于Hoare方案的劃分，而紅色條對應(yīng)于循環(huán)劃分算法。

劃分算法針對5種不同的情況運行，基于“l(fā)eft_part_percent”——劃分后出現(xiàn)的數(shù)組左半部分的百分比（N）。時間以納秒為單位。

現(xiàn)在，我們看到了一個明顯的相關(guān)性：循環(huán)劃分比Hoare方案表現(xiàn)得更好，因為“l(fā)eft_part_percent”接近50%。換句話說，當(dāng)劃分后數(shù)組的左右部分看起來長度更近時，循環(huán)劃分的工作速度相對更快。這也是一種預(yù)期的行為。

實驗結(jié)果說明

第一個問題：為什么當(dāng)“l(fā)eft_part_percent”接近50%時，劃分通常需要更長的時間呢？

讓我們想象一下一個極端情況——劃分后幾乎所有值都出現(xiàn)在左（或右）部分。這意味著，數(shù)組的幾乎所有值都小于（或大于）基準(zhǔn)值。這意味著，在掃描過程中，所有這些值都被認為已經(jīng)處于最終位置，并且執(zhí)行的值賦值很少。如果試著想象另一種情況——當(dāng)劃分后左右部分的長度幾乎相等時，這意味著執(zhí)行了大量的值賦值（因為最初所有值在數(shù)組中都是隨機混洗的）。

第二個問題：在查看“大型對象”的劃分時，為什么當(dāng)“l(fā)eft_part_percent”接近50%時，兩種算法的運行時間差異會變得更大？

前面的解釋表明，當(dāng)“l(fā)eft_part_percent”接近50%時，需要在數(shù)組中進行更多的值賦值。在前面的幾節(jié)中，我們還表明，與Hoare方案相比，循環(huán)劃分總是使值賦值減少1.5倍。因此，當(dāng)我們通常需要對數(shù)組中的值進行更多重新排列時，1.5倍的差異對整體運行時間的影響更大。

第三個問題：為什么對“大對象”進行劃分時的絕對時間（以納秒為單位）比對32位整數(shù)進行劃分時大？

這個方法很簡單——因為將一個“大對象”分配給另一個對象比將一個原始數(shù)據(jù)類型分配給其他類型需要更多的時間。

此外，我還對不同長度的數(shù)組進行了所有實驗，但總體情況沒有改變。

7.結(jié)論

在本文中，我介紹了一種經(jīng)過修改的劃分方案，稱為“循環(huán)劃分”。與目前使用的Hoare劃分方案相比，它總是能夠減少1.5倍的值賦值。

當(dāng)然，在對序列進行劃分時，值賦值并不是唯一執(zhí)行的操作類型。除此之外，劃分算法檢查輸入序列“A”的值是否小于或大于基準(zhǔn)值“p”，以及它們對“A”上的索引進行遞增和遞減。比較、增量和減量的數(shù)量不會受到引入“循環(huán)劃分”的影響，因此我們不能指望它的運行速度快1.5倍。然而，當(dāng)對復(fù)雜數(shù)據(jù)類型的數(shù)組進行劃分時，其中值賦值比簡單地遞增或遞減索引要耗時得多，整個算法的運行速度實際上可以快1.5倍。

劃分過程是快速排序算法的主要程序，也是查找未排序數(shù)組中值或查找其k階統(tǒng)計量的算法的主要例程。因此，在處理復(fù)雜數(shù)據(jù)類型時，我們還可以預(yù)期這些算法的性能提高1.5倍。

除非另有說明，本文中所有使用的圖像均按作者本人要求而設(shè)計。

參考文獻

【1】——C++中循環(huán)劃分的實現(xiàn)：https://github.com/tigranh/cyclic_partition。

譯者介紹

朱先忠，51CTO社區(qū)編輯，51CTO專家博客、講師，濰坊一所高校計算機教師，自由編程界老兵一枚。

原文標(biāo)題：Cyclic Partition: An Up to 1.5x Faster Partitioning Algorithm，作者：Tigran Hayrapetyan