一种高效的顺序划分算法

摘要：本文将详细引见一种陈腐高效的顺序划分算法——循环划分算法，它能够对个别类型值数据启动最小次数的从新陈列。

1.导言

顺序划分是计算机编程中一种基本且罕用的算法。给定一个数字序列“A”和一个称为基准值的值“p”，划分算法的目标是以这种方式从新陈列“A”中的数字，使一切小于“p”的数字排在第一位，而后是其他的数字。

按基准值“p=20”划分前后的序列示例。运行算法后，一切小于20的值（浅绿色）显示在其他值之前（黄色）。

划分算法有不同的运行，但最受欢迎的运行包括：

对序列启动排序是在少量数据上成功更快导航的关键步骤。在两种经常出现的搜查算法中——线性搜查和二分查找——后者只要在数组中的数据被排序时能力经常使用。找到中位数或k阶统计量关于了解给定未排序数据中的值散布至关关键。

目前曾经存在不同的划分算法（也称为划分打算），但最驰名的要算是“Lomuto打算”和“Hoare打算”。Lomuto打算通常直观上更容易了解，而Hoare打算在给定数组内的重排次数较少，这就是它在通常中通常更受欢迎的要素。

在本文中，我要介绍的是一种新的划分打算，称为“循环划分”，它相似于Hoare打算，但数组内的从新陈列（值赋值）要少1.5倍。因此，正如稍后将显示的那样，值赋值的数量简直等于最后“不在原位”的值的数量，并且应该以某种方式移动。这一理想让我以为这个新的划分打算简直是最优的。

接上去的内容按以下方式组织：

请留意，GitHub上曾经提供了基于C++言语的循环划分的成功，以及它与规范Hoare打算的基准测试，详见本文末尾的援用文献。

2.原地顺序划分回忆

假设输入和输入序列位于计算机内存中的2个不同数组中，则对序列启动划分将不是一项艰难的义务。假设状况是这样的话，那么其中一种方法或许是：

以下是运转此类算法的几个形态：

在第一阶段，咱们计算出只要7个值小于“p=20”（浅绿色的值），因此咱们预备从索引7开局将较大的值写入输入序列。

在第二阶段扫描输入序列的5个值之后，咱们将其中的3个附加到输入序列的左侧局部，另两个在其右侧。

继续第二阶段，咱们如今从输入序列中扫描了9个值，将其中5个搁置在输入序列的左侧，将另外4个搁置在其右侧。

算法成功（如今，输入序列的两个局部都已正确填充到末尾）

留意，这里保管了左边局部或左边局部中数值的相对顺序（依据它们最后在输入数组中的写入方式）。

当然，还有其他更冗长的处置打算，比如代码中只要一个循环的处置打算。

如今，当咱们不想经常使用任何额外的内存时，艰难就来了。因此，只要在惟一的数组中移动值，输入序列就会被转换为划分后的输入序列。顺便说一句，这种不经常使用额外内存的算法称为就地算法。

用相反的基准值“p=20”对相反的输入序列“A”启动划分

这里显示的值顺序对应于序列的输入形态，每个值都显示箭头——假设应该将该值移动到某处，以便对整个序列启动划分。

在引见我的划分打算之前，让咱们首先来回忆一下现有的和罕用的就地划分处置打算。

3.目前经常使用的划分打算

在观察了各种编程言语的规范库中排序的一些成功后，看起来经常使用最宽泛的划分算法是Hoare打算。我发现它被用于例如：

在基于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打算，并前往结果左边局部第一个值的索引。    Array  Integers  Integer   Integer         // 依据须要向左移动索引“i”  i  j and i  p   i // 依据须要向右移动索引“j”  i  j and j  p   j   i  j  i  j and i  p  i    i    i i  j j  tmp    i   j

在第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次赋值。

须要强调一下，“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]”的最后一个值。

要做到这一点，所需的操作是：

情景2：循环左移3个位置

在下一个例子中，咱们依然想对同一序列启动循环左移，但如今向左移动3个

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

咱们看到值A[0]、A[3]、A[6]和A[9]正在相互替换（蓝色箭头）

并且由于值A[2]、A[5]、A[8]和A[11]仅在彼此之间替换（黄色箭头）。

“tmp”变量被赋值和读取了3次。

这里咱们有3个独立的赋值链/循环，每个长度为4。

为了在A[0]、A[3]、A[6]和A[9]之间正确替换值，须要采取以下执行：

……这里启动了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替换，因此赋值的总数为：

与“A”相反的赋值确实切顺序是：

小结

咱们曾经看到，从新陈列相反序列“A”的值或许须要不同数量的赋值，详细取决于从新陈列值确实切方式。

在所提供的3个示例中，序列的长度一直为N=12，但所需调配的数量不同：

更确切地说，赋值次数等于N+C，其中“C”是重排环节中发生的循环次数。在这里，我所说的“循环”是指“a”的变量子集，其值在彼此之间旋转。

在咱们的例子1（左移1）中，咱们只要C=1个赋值循环，“A”的一切变量都介入了这个周期。这就是为什么赋值总数是：

在情景2（左移3）中，咱们有C=3个赋值循环，其中：

第二个循环运行于变量（A[1]、A[4]、A[7]、A[10]）

第三个循环运行于变量（A[2]，A[5]，A[8]，A[11]）。

这就是为什么赋值总数是：

在咱们的情景3（反转）中，咱们有⌊N/2⌋=12/2=6个周期。这些都是最短的或许循环，并运行于配对（A[0]，A[11]），（A[1]，A[10]），…等等。这就是为什么赋值的总数是：

当然，在所提供的示例中，赋值数量的相对差异十分小，在编写高功能代码时不会起任何作用。但这是由于咱们思考了一个长度为“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”值移动到它上方之后，咱们将获取一个代替的划分序列。

那么，咱们在这里干什么呢？

正如咱们所看到的，这里咱们只要一个遍历一切“L”值的赋值循环，为了正确地从新陈列它们，与Hoare打算的“3*L/2”赋值相比，只要要“L+1”值赋值。

我更青睐将这种新的划分打算称为“循环划分”，由于一切应该以某种方式从新陈列的“L”值如今都位于一个赋值循环中。

上方给出的是循环划分算法的伪代码。与Hoare打算的伪代码相比，这些变动微无余道，但如今咱们将少做1.5倍的义务。

// 经过“循环划分”打算将序列A[0..N）与枢轴值'p'启动划分，//并前往结果右侧局部的第一个值的索引。    Array  Integers  Integer   Integer       // 找到左边第一个不在其位置的值  i   and i  p   i  i         i    // 依据须要向右移动索引“j”  i  j and j  p   j  i  j    i  j   i //依据须要向左移动索引“i”  i  j and i  p   i  i  j    j  i   j  j  tmp   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”值是相互替换的值。所以咱们有：

这象征着，“L”实践上是应该以某种方式从新陈列的最小数量的值，以便对序列启动划分。循环划分算法仅经过“L+1”赋值从新陈列它们。这就是我准许自己将这种新的划分打算称为“近乎最优”的要素。

6.试验结果

曾经证实，新的划分打算执行的值赋值更少，因此咱们可以预期它运转得更快。但是，在颁布算法之前，我也想以试验的方式搜集结果。

我比拟了经常使用Hoare打算和循环划分启动划分时的运转期间。一切试验都是在随机乱序的数组中启动的。

试验中，经常使用的不同的参数有：

对原始数据类型的数组启动划分

以下是对原始数据类型（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倍。

除非另有说明，本文中一切经常使用的图像均按作者自己要求而设计。

参考文献

译者引见

朱先忠，社区编辑，专家博客、讲师，潍坊一所高校计算机老师，自在编程界老兵一枚。

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