我的Quicksort在对预排序项目进行排序时失败,如何改进?

问题描述 投票:0回答:1

这是一个标准的递归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);
}
c++ sorting quicksort implementation
1个回答
0
投票

我认为您的问题是关键价值的选择。您正在使用最右边的值(array[count-1]),对于已排序的序列,该值可能会导致worst-case behavior。您创建一个大小为1的分区,并创建另一个大小为n-1的分区。这会导致n-1个递归调用链,从而导致性能不佳 O(N 2)或堆栈溢出。

您应该考虑其他替代方法,例如:

  • 随机索引
  • 中间索引
  • [三个索引的中位数(第一,中间,最后)] >>
  • 像中位数(ninther)一样复杂的事情>
© www.soinside.com 2019 - 2024. All rights reserved.