这是一个标准的递归quickSort实现,它成功地对未排序项的较大列表进行了排序,但未对“预排序”项进行排序。我知道这将花费更长的时间,但不会完全失败。有没有可能的改进?
void quickSort(int *array, size_t count) {
int pivot = array[count - 1];
int max_index = 0;
for (size_t i = 0; i < count - 1; ++i)
{
if (array[i] < pivot) {
swap(array[i], array[max_index]);
++max_index;
}
}
swap(array[max_index], array[count - 1]);
if (max_index > 1)
quickSort(array, max_index);
if (count - max_index - 1 > 1)
quickSort(array + max_index + 1, count - max_index - 1);
}
我认为您的问题是关键价值的选择。您正在使用最右边的值(array[count-1]
),对于已排序的序列,该值可能会导致worst-case behavior。您创建一个大小为1的分区,并创建另一个大小为n-1的分区。这会导致n-1个递归调用链,从而导致性能不佳 O(N 2)或堆栈溢出。
您应该考虑其他替代方法,例如: