我正在做一些练习题来刷新我的旧算法课程,并且我正在尝试实现快速排序。是的,我知道我们应该在生产代码中使用std::sort
,但这是出于教育目的:)
我有下面的代码。它在数组中的所有元素都是唯一的时候有效,但在有重复元素时无效。怎么会?我在哪里动摇了?
void quicksort(int arr[], int left, int right)
{
// base case:
if (left >= right)
return;
// alternative case:
int pivot_index = (left + right)/2;
int pivot = arr[pivot_index];
int i = left, j = right;
int tmp;
while (i < j)
{
// scan from left until elem > pivot or left == right,
while (arr[i] < pivot)
++i;
// scan from right until elem < pivot or right == left.
while (arr[j] > pivot)
--j;
if (i < j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
++i;
--j;
}
}
// recurse on left and right.
if (i > left)
quicksort(arr, left, i);
if (i < right)
quicksort(arr, i + 1, right);
}
void main()
{
const int arr_size = 7;
int arr[arr_size] = {1,2,4,3,9,5,2};
quicksort(arr, 0, arr_size - 1);
for (int i = 0; i < arr_size; ++i)
{
std::cout << arr[i] << ", ";
}
}