这是在许多地方找到的 quick_sort 的实现，包括 wikipedia .
这是我的简单概要。
- 选择一个枢轴元素 – 左边和右边的 ½。
- 从右边开始索引并向左迭代。
- 如果 Elements[right] < P 选择翻转。
- 在左边开始索引并在右边迭代。
- 如果 Elements[left] > P 选择作为翻转。
- 翻转两个元素。
- 重复轴心点
- 对每一半递归重复
谁能解释一下两条递归线背后的原因:
if (left < j)quick_sort(arr, left, j);
if (i < right)quick_sort(arr, i, right);
片段:
void quick_sort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j)
{
while (arr[i] < pivot)i++;
while (arr[j] > pivot)j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (left < j)quick_sort(arr, left, j);
if (i < right)quick_sort(arr, i, right);
}
最佳答案
如果你从一个数组开始:
[74, 32, 39, 15, 25, 82, 23, 2, 97, 62, 95, 34, 92, 84, 28]
它选择中间的元素 (23)，然后划分:
[15 2 ] 23 [ 32 74 32 39 25 82 97 62 95 34 92 84 28]
请注意，列表未排序。由于左边不止一个，它调用自己对左边分区进行排序。
[15 2 ] ...
它选择中间 (15) 和分区:
[2] 15 ...
然后因为左边(1个元素)和右边(0个元素)都小于两个元素，它返回。
2 15 23 [74 32 39 25 82 97 62 95 34 92 84 28]
现在右边还有多个元素，所以调用自己对右边分区进行排序。
... [74 32 39 25 82 97 62 95 34 92 84 28]
它选择中间 (97) 和分区:
... [74 32 39 25 82 62 95 34 92 84 28] 97
现在left已经不止一个元素了，所以调用自己对left parition进行排序...
...等等
最终它到达所有子集都已排序的点，并返回到第一个:
2 15 23 25 28 32 34 39 62 74 82 84 92 95 97
完成了!
(我不是故意选择不好的支点，excel 为我选择了数字。很好的例子是有时支点不是很好。)
关于c++ - quick_sort 的递归部分是如何工作的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7813276/