我一直在研究《程序员面试金典》(第五版,第119页)中的分区函数。我将其复制如下:
int partition(int arr[], int left, int right){
int pivot = arr[(left + right) /2 ]; // Pick pivot point
while (left <= right) {
// Find element on left that should be on right
while (arr[left] < pivot) left++;
// Find the element on right that should be on left
while (arr[right] > pivot) right--;
// Swap elements, and move left and right indicies
if (left <= right) {
swap(arr, left, right); // swaps elements
left++;
right--;
}
}
return left;
}
给定以下数组:
1 2 3 4 5 6 3
这是我按步骤进行分区的方法:
- 4是枢轴值。左边=0,右边=6
左边=3,右边=6。交换。
1 2 3 3 5 6 4
左边=4,右边=4。退出
1 2 3 3 5 6 4
分区的结果不是4。我是否跟错了步骤,还是算法有误?我已经仔细检查了算法的复制过程,并且正确地复制了它。
另外,我不确定为什么分区返回左侧,是返回枢轴吗?
我理解维基百科对于分区和快速排序的实现,但我正在努力理清楚这里发生了什么。
left
和right
分别代表什么吗? - LastStar007