譯者 | 朱先忠

審校 | 重樓

摘要：本文將詳細介紹一種新穎高效的順序劃分算法——循環劃分算法，它能夠對普通類型值數據進行最小次數的重新排列。

1.導言

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

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

劃分算法有不同的應用，但最受歡迎的應用包括：

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

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

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

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

接下來的內容按以下方式組織：

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

請注意，GitHub上已經提供了基于C++語言的循環劃分的實現，以及它與當前標準Hoare方案的基準測試，詳見本文末尾的引用文獻。

2.原地順序劃分回顧

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

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

以下是運行此類算法的幾個狀態：

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

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

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

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

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

當然，還有其他更簡短的解決方案，比如代碼中只有一個循環的解決方案。

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

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

這里顯示的值順序對應于序列的輸入狀態，每個值都顯示箭頭——如果應該將該值移動到某處，以便對整個序列進行劃分。

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

3.目前使用的劃分方案

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

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

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

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

長度為'N'的輸入序列“A”，應按基準值“p=20”進行劃分

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

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

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

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

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

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

// 對序列A[0..N)進行劃分，使用基準值 'p' 
// 根據Hoare方案，并返回結果右邊部分第一個值的索引。
function partition_hoare( A[0..N) : Array of Integers, p: Integer ) : Integer
 i := 0
 j := N-1
 while true
 // 根據需要向左移動索引“i”
 while i < j and A[i] < p
 i := i+1
 // 根據需要向右移動索引“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行中，我們為2次掃描設置了開始索引。

第8-10行從左側搜索這樣一個值，該值在劃分后應屬于右側。

同樣，第11-13行從右側搜索這樣一個值，它應該屬于左側。

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

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

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

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

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

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

這些任務是：

tmp := a

a := b

b := tmp

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

4.循環賦值

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

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

情形1：序列的循環左移

如果我們想將序列“A”循環左移1個位置，應該完成多少個賦值操作？

長度為N=12的序列“A”的循環左移示例

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

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

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

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

……這導致了13次賦值操作。

情形2：循環左移3個位置

在下一個例子中，我們仍然想對同一序列進行循環左移，但現在向左移動3個位置：

序列“A”的循環左移3的示例，長度N=12

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

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

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

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

這里我們有3個獨立的賦值鏈/循環，每個長度為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]）內交換值將需要分別進行5次賦值。將所有這些加在一起，得到了將序列“A”循環左移3所需的5*3=15個賦值，其中N=12個值。

情形3：顛倒順序

當反轉長度為“N”的序列“A”時，執行的操作是：

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

反轉數組“A”的示例，其中N=12個值

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

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

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

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

tmp := A[0] // 循環1
A[0] := A[11]
A[11] := tmp
tmp := A[1] // 循環2
A[1] := A[10]
A[10] := tmp

...

tmp := A[5] // 循環6
A[5] := A[6]
A[6] := tmp

小結

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

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

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

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

N+C=12+1=13。

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

變量內的第一個循環（A[0]、A[3]、A[6]、A[9]）

第二個循環應用于變量（A[1]、A[4]、A[7]、A[10]）

第三個循環應用于變量（A[2]，A[5]，A[8]，A[11]）。

這就是為什么賦值總數是：

N+C=12+3=15。

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

N+C=12+6=18。

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

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

5.優化Hoare劃分方案

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

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

給定基準值“p=20”，應重新排列的“L=8”值是朝箭頭方向（或離開箭頭方向）。

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

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

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

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

更改后的劃分方案，應用于相同的序列“A”

由于基準值“p=20”沒有改變，因此應重新排列的“L=8”值也相同。

所有箭頭代表新方案中唯一的賦值循環。

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

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

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

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

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

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

// 通過“循環劃分”方案將序列A[0..N）與樞軸值'p'進行劃分，
//并返回結果右側部分的第一個值的索引。
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值都移到左側
 //下面開始循環賦值
 tmp := A[i] // 唯一一次寫向變量'tmp'
 while true
 // 根據需要向右移動索引“j”
 while i < j and A[j] >= p
 j := j-1
 if i == j // 檢查掃描是否完成
 break
 //循環中的下一個賦值
 A[i] := A[j]
 i := i+1
 //根據需要向左移動索引“i”
 while i < j and A[i] < p
 i := i+1
 if i == j // 檢查掃描是否完成
 break
 // 循環中的下一個賦值
 A[j] := A[i]
 j := j-1
 // 掃描已經完成
 A[j] := tmp // 唯一一次讀變量'tmp'
 return j

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

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

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

第15-19行從右側搜索這樣的值“a[j]”，該值應移動到左側。一旦找到，第20-22行將其放入索引“i”處的空位中，之后索引“j”處的位置變為空，并等待另一個值。

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

這種模式在算法的主循環中繼續，在第14-30行。

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

最后一行返回該索引。

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

該算法的時間復雜度也是O（N），因為我們仍然從兩端掃描序列。它只會減少1.5倍的值賦值，因此加速僅反映在常數因子中。

注意：GitHub網站上提供了C++語言中循環劃分的實現，且在本文末尾引文中也有提供。

我還想證明，無論我們使用什么劃分方案，Hoare方案中的值“L”都不能降低。假設劃分后，左部分的長度為“left _n”，右部分的長度也為“right _n”。現在，如果查看原始未劃分數組的左對齊“left_n”長區域，我們會在那里找到一些“t1”值，這些值不在它們的最終位置。因此，這些值大于或等于“p”，無論如何都應該移動到右側。

劃分前后順序的圖示

左側部分的長度為“left_n=7”，右側部分的長度是“right_n=5”。

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

它們大于“p=20”（黃色），應該以某種方式移動到右側。

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

它們小于“p”（淺綠色的），應該以某種方式移動到左側。

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

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

t1 = t2 = L/2,

或者：

t1 + t2 = L.

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

6.實驗結果

已經證明，新的劃分方案執行的值賦值更少，因此我們可以預期它運行得更快。然而，在發布算法之前，我也想以實驗的方式收集結果。

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

實驗中，使用的不同的參數有：

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

對原始數據類型的數組進行劃分

以下是對原始數據類型（32位整數）的數組運行劃分算法的結果：

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

藍色條對應于Hoare方案的劃分，而紅色條對應于循環劃分算法。

劃分算法針對5種不同的情況運行，基于“left_part_percent”——劃分后出現的數組左半部分的百分比（N）。時間以納秒為單位。

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

對“大型對象”數組進行劃分

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

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

其中，藍色條對應于Hoare方案的劃分，而紅色條對應于循環劃分算法。

劃分算法針對5種不同的情況運行，基于“left_part_percent”——劃分后出現的數組左半部分的百分比（N）。時間以納秒為單位。

現在，我們看到了一個明顯的相關性：循環劃分比Hoare方案表現得更好，因為“left_part_percent”接近50%。換句話說，當劃分后數組的左右部分看起來長度更近時，循環劃分的工作速度相對更快。這也是一種預期的行為。

實驗結果說明

第一個問題：為什么當“left_part_percent”接近50%時，劃分通常需要更長的時間呢？

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

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

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

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

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

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

7.結論

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

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

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

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

參考文獻

【1】——C++中循環劃分的實現：https://github.com/tigranh/cyclic_partition。

譯者介紹

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

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