一種高效的順序劃分算法——循環(huán)劃分算法

作者：朱先忠 2024-11-01 08:00:00

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

譯者 | 朱先忠

審校 | 重樓

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

1.導(dǎo)言

順序劃分是計(jì)算機(jī)編程中一種基本且常用的算法。給定一個(gè)數(shù)字序列“A”和一個(gè)稱為基準(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ù)期的線性時(shí)間內(nèi)找到中值。

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

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

在本文中，我要推薦的是一種新的劃分方案，稱為“循環(huán)劃分”，它類似于Hoare方案，但數(shù)組內(nèi)的重新排列（值賦值）要少1.5倍。因此，正如稍后將顯示的那樣，值賦值的數(shù)量幾乎等于最初“不在原位”的值的數(shù)量，并且應(yīng)該以某種方式移動(dòng)。這一事實(shí)讓我認(rèn)為這個(gè)新的劃分方案幾乎是最優(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é)將對(duì)小數(shù)據(jù)類型和大數(shù)據(jù)類型的數(shù)組進(jìn)行Hoare方案和循環(huán)劃分的實(shí)驗(yàn)比較。

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

2.原地順序劃分回顧

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

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

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

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

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

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

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

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

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

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

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

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

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

3.目前使用的劃分方案

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

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

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

讓我們?cè)诹硪粋€(gè)例子中觀察Hoare方案：

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

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

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

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

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

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

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

// 對(duì)序列A[0..N)進(jìn)行劃分，使用基準(zhǔn)值 'p' 
// 根據(jù)Hoare方案，并返回結(jié)果右邊部分第一個(gè)值的索引。
function partition_hoare( A[0..N) : Array of Integers, p: Integer ) : Integer
 i := 0
 j := N-1
 while true
 // 根據(jù)需要向左移動(dòng)索引“i”
 while i < j and A[i] < p
 i := i+1
 // 根據(jù)需要向右移動(dòng)索引“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è)搜索這樣一個(gè)值，該值在劃分后應(yīng)屬于右側(cè)。

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

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

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

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

該算法的時(shí)間復(fù)雜度為O（N），無論兩次掃描在哪里相遇，因?yàn)樗鼈兛偸且黄饞呙鐽個(gè)值。

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

交換2個(gè)變量“a”和“b”的值，需要在“tmp”變量的幫助下進(jìn)行3次賦值。

這些任務(wù)是：

tmp := a

a := b

b := tmp

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

4.循環(huán)賦值

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

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

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

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

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

我們看到所需的賦值操作數(shù)量為N+1=13，因?yàn)槲覀冃枰?/span>

1）將“A[0]”存儲(chǔ)在臨時(shí)變量“tmp”中，然后

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

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

要做到這一點(diǎn)，所需的操作是：

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個(gè)位置

在下一個(gè)例子中，我們?nèi)匀幌雽?duì)同一序列進(jìn)行循環(huán)左移，但現(xiàn)在向左移動(dòng)3個(gè)位置：

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

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

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

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

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

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

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

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

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

情形3：顛倒順序

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

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

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

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

由于每個(gè)交換都需要3次賦值，而對(duì)于反轉(zhuǎn)整個(gè)序列“A”，我們需要進(jìn)行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個(gè)示例中，序列的長(zhǎng)度始終為N=12，但所需分配的數(shù)量不同：

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

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

N+C=12+1=13。

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

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

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

第三個(gè)循環(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個(gè)周期。這些都是最短的可能循環(huán)，并應(yīng)用于配對(duì)（A[0]，A[11]），（A[1]，A[10]），…等等。這就是為什么賦值的總數(shù)是：

N+C=12+6=18。

當(dāng)然，在所提供的示例中，賦值數(shù)量的絕對(duì)差異非常小，在編寫高性能代碼時(shí)不會(huì)起任何作用。但這是因?yàn)槲覀兛紤]了一個(gè)長(zhǎng)度為“N=12”的非常短的數(shù)組。對(duì)于較長(zhǎng)的數(shù)組，賦值數(shù)量的差異將與N成比例增長(zhǎng)。

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

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

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

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

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

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

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

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

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

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

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

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

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

那么，我們?cè)谶@里干什么呢？

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

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

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

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

// 通過“循環(huán)劃分”方案將序列A[0..N）與樞軸值'p'進(jìn)行劃分，
//并返回結(jié)果右側(cè)部分的第一個(gè)值的索引。
function partition_cyclic( A[0..N) : Array of Integers, p: Integer ) : Integer
 i := 0
 j := N-1
 // 找到左邊第一個(gè)不在其位置的值
 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ù)需要向右移動(dòng)索引“j”
 while i < j and A[j] >= p
 j := j-1
 if i == j // 檢查掃描是否完成
 break
 //循環(huán)中的下一個(gè)賦值
 A[i] := A[j]
 i := i+1
 //根據(jù)需要向左移動(dòng)索引“i”
 while i < j and A[i] < p
 i := i+1
 if i == j // 檢查掃描是否完成
 break
 // 循環(huán)中的下一個(gè)賦值
 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è)。如果事實(shí)證明沒有這樣的值，并且所有N個(gè)項(xiàng)目都屬于左側(cè)部分，則第10行和第11行會(huì)報(bào)告這一點(diǎn)并完成算法。

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

第15-19行從右側(cè)搜索這樣的值“a[j]”，該值應(yīng)移動(dòng)到左側(cè)。一旦找到，第20-22行將其放入索引“i”處的空位中，之后索引“j”處的位置變?yōu)榭?，并等待另一個(gè)值。

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

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

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

最后一行返回該索引。

這樣我們就可以在循環(huán)體中一起編寫循環(huán)的2個(gè)賦值，因?yàn)檎绲?節(jié)所證明的那樣，“L”總是偶數(shù)。

該算法的時(shí)間復(fù)雜度也是O（N），因?yàn)槲覀內(nèi)匀粡膬啥藪呙栊蛄?。它只?huì)減少1.5倍的值賦值，因此加速僅反映在常數(shù)因子中。

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

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

劃分前后順序的圖示

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

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

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

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

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

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

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

t1 = t2 = L/2,

或者：

t1 + t2 = L.

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

6.實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

劃分算法針對(duì)5種不同的情況運(yùn)行，基于“l(fā)eft_part_percent”——?jiǎng)澐趾蟪霈F(xiàn)的數(shù)組左半部分的百分比（N）。時(shí)間以納秒為單位。

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

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

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

大對(duì)象數(shù)組上劃分算法的運(yùn)行時(shí)間（256個(gè)隨機(jī)16位整數(shù)的長(zhǎng)靜態(tài)數(shù)組），長(zhǎng)度N=10000

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

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

實(shí)驗(yàn)結(jié)果說明

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

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

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

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

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

這個(gè)方法很簡(jiǎn)單——因?yàn)閷⒁粋€(gè)“大對(duì)象”分配給另一個(gè)對(duì)象比將一個(gè)原始數(shù)據(jù)類型分配給其他類型需要更多的時(shí)間。

此外，我還對(duì)不同長(zhǎng)度的數(shù)組進(jìn)行了所有實(shí)驗(yàn)，但總體情況沒有改變。

7.結(jié)論

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

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

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

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