快速排序实现不适用于重复键 [英] QuickSort implementation does not work for duplicate key
本文介绍了快速排序实现不适用于重复键的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我尝试实现快速排序。它工作得很好,除非有重复的键,在这种情况下会有一个无限循环,并且永远不会结束。你能帮我弄明白我做错了什么吗?
// quick sort
void quickSort(int arr[], const unsigned size)
{
// base case
if (size < 2)
return;
int pivot = arr[size / 2];
unsigned L = 0, U = size - 1;
// partitioning
while (L < U) {
while (arr[L] < pivot)
L++;
while (arr[U] > pivot)
U--;
swap(&arr[L], &arr[U]);
}
quickSort(arr, L); // sort left array
quickSort(&arr[U + 1], size - L - 1); // sort right array
}
推荐答案
您有小于和大于条件。但不存在=
的条件。这就是它将运行无限循环的原因。将它们更改为<=
和>=
。
这篇关于快速排序实现不适用于重复键的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文