请考虑快速排序"lomuto分区"；来自经典算法教科书算法简介的方案，作者：Cormen，Leiserson，Rivest&施坦。
PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1
在实现这个算法后，我发现它不能正常工作，最多会偏离1个元素。然后，我开始计算一个解决方案，并最终得出了以下有效的C代码。我已经在代码中评论了算法是如何工作的。
int quickSortPartition(int *array, int beginIndex, int endIndex) // end index = array length - 1.
{
int pivotIndex = beginIndex; // first element as pivot.
int pivotValue = array[pivotIndex]; // initial pivot value.
int i = beginIndex + 1; // start loop with i being 2nd index.
while(i < endIndex) // loop running until end of array.
{
if(array[i] > array[i + 1]) // comparing the 2 elements ahead of pivot.
{
swap(array, i, i + 1); // swapping the 2 elements if prev element > next element.
}
if(array[i] < pivotValue) // comparing element at pivot index with the next index element.
{
swap(array, pivotIndex, i); // swapping if next element is less than element at pivot index.
++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
}
++i; // drive loop.
}
if(array[pivotIndex] > array[pivotIndex + 1]) // at the very end, compare whether the element to the right of pivot is > element at pivot index.
{
swap(array, pivotIndex, pivotIndex + 1); // swapping if next element is less than element at pivot index.
++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
}
return pivotIndex; // returning new pivot index.
}
我的实现是否不如书中所谓的"；洛穆托分区；？当然，它们都是O(n(，但在数字原子运算方面呢，比如赋值&在一次迭代中进行比较？它对大规模案例的效率有显著影响吗？为什么这本书的算法不起作用？它缺了什么？对于如何进一步简化我的代码，我也将不胜感激。
其他后续信息：
- 我已经用python实现了这本书的代码
def quicksort(A, p, r):
if p < r:
q = partition(A, p, r)
quicksort(A, p, q - 1)
quicksort(A, q + 1, r)
def partition(A, p, r):
x = A[r]
i = p - 1
for j in range(p, r - 1):
if A[j] <= x:
i = i + 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[r] = A[r], A[i + 1]
return i + 1
array = [2, 55, 43, 12, 65, 72, 41, 18, 6]
print(array)
quicksort(array, 0, len(array) - 1)
print(array)
结果：
unsorted: [2, 55, 43, 12, 65, 72, 41, 18, 6]
sorted: [2, 6, 41, 43, 12, 55, 65, 72, 18]
如您所见，排序失败。此外，如果我使用len(数组(作为第三个参数，就会出现溢出错误。
- 至于我的C代码，它使用了我的算法并有效，这是我的头文件，你可以测试一下
#ifndef A1_H
#define A1_H
// am1n
#include<stdio.h>
#include<stdlib.h>
void printArray(int *array, int arrayLength)
{
int i = 0;
--arrayLength;
for(i = 0; i < arrayLength; ++i)
{
printf("%d, ", array[i]);
}
printf("%d.n", array[i]);
}
void swap(int *array, int a, int b)
{
if(array[a] != array[b])
{
int tempValue = array[a];
array[a] = array[b];
array[b] = tempValue;
}
}
int fastSortPartition(int *array, int beginIndex, int endIndex) // end index = array length - 1.
{
int pivotIndex = beginIndex; // first element as pivot.
int pivotValue = array[pivotIndex]; // initial pivot value.
int i = beginIndex + 1; // start loop with i being 2nd index.
while(i < endIndex) // loop running until end of array.
{
if(array[i] > array[i + 1]) // comparing the 2 elements ahead of pivot.
{
swap(array, i, i + 1); // swapping the 2 elements if prev element > next element.
}
if(array[i] < pivotValue) // comparing element at pivot index with the next index element.
{
swap(array, pivotIndex, i); // swapping if next element is less than element at pivot index.
++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
}
++i; // drive loop.
}
if(array[pivotIndex] > array[pivotIndex + 1]) // at the very end, compare whether the element to the right of pivot is > element at pivot index.
{
swap(array, pivotIndex, pivotIndex + 1); // swapping if next element is less than element at pivot index.
++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
}
return pivotIndex; // returning new pivot index.
}
void fastSort(int *array, int beginIndex, int endIndex)
{
if(beginIndex < endIndex)
{
int pivotIndex = fastSortPartition(array, beginIndex, endIndex);
fastSort(array, beginIndex, pivotIndex - 1);
fastSort(array, pivotIndex + 1, endIndex);
}
}
#endif
设N为正在处理的子数组中的元素数
设L为最终落入数组左侧部分的项目数——小于或等于原始算法中的pivot，小于pivot加上代码中pivot本身。
两个例程都必须在数组中执行N-1个步骤，并进行N-1个比较，以检查每个元素，并确定那些小于或等于轴心的元素。而最初的程序正是进行了这么多的比较。但是您的代码做了两倍的工作：在循环的每次迭代中，它都会比较array[i]和pivotValue以及array[i]和array[i + 1]。
这两个例程还必须进行几乎完全L的交换，以将这些较小的项目组合在一起，再加上最多两次交换，以临时将枢轴移开并返回原位。但是，您的代码可能会进行多达N-1次的额外交换，以向右推动"大"元素，而不会带来显著收益。
所以答案是：不，无论是在多次比较还是交换中，你提出的代码肯定不会比原始算法更高效。
您的代码所做的工作(基本操作(大约是Lomuto方法的两倍。但这只是一个比例因子；当事物渐近时，它们都是线性的，O(N(。
事实证明我是对的：您的实现不是Lomuto算法——由于for j in range()的使用不正确，您没有按照原始例程的要求测试数组的最后一项。
将循环的上限更改为适当的值可以解决问题
for j in range(p, r):
请注意，Python的范围不包括右边界，pivot保持在最后，直到分区结束
示例的结果
[2, 6, 12, 18, 41, 43, 55, 65, 72]