排序到底是什么——快速排序

发布于 2024-11-03 06:53:10 字数 1015 浏览 0 评论 0原文

我们必须为我们自己的 Comparable 基类进行优化的快速排序。为了我的一生，我无法让它发挥作用。该算法看起来很简单，但是我无法让我的代码正常工作。我有一个 DateTime 类，它扩展了我用来测试的 Comparable，并且排序似乎可以工作，但是大约每 20 个运行中就有一个运行单个值不合适，并且当我对数组的块使用插入排序时，该值较少超过8，整个排序就会变得不正常。

在我的分区方法中，当我将枢轴移动到末尾并在开始和结束 - 1 处启动指针时，它会起作用。我想将枢轴移动到末尾 - 1 因为第一个和最后一个已经排序并开始指针首先是 + 1，最后是 -2，但是如果我尝试这样做，一切都会崩溃，但我不明白为什么。

所以我现在有一些有用的东西。当我不在较小的子数组上使用插入排序时，它会变得有点痉挛，这很麻烦，但最终会弄清楚。感谢 ben j 指出了从数组中掉出的情况......这导致了插入排序问题。 :)

我当前的代码如下

    Comparable** partition(Comparable** from, Comparable** to)
{
    Comparable** pivot  = from + (to - from) / 2;
    SortFirstMiddleLast(from, pivot, to - 1);
    swap(*pivot, *to);
    pivot = to;
    ++from; to -= 2;
    while (from <= to)
    {
        while (**from <= **pivot && from <= to) ++from;
        while (**to   >= **pivot && from <= to) --to;
        if (from < to)
        {
            swap(*from, *to);
            ++from; --to;
        }
    }
    swap(*from, *pivot);
    return from;
}

原文

We have to make an optimized quicksort for out own Comparable base class. For the life of me I cannot make it work. The algorithm seems straight forward, however I cannot seen to get my code to work. I have a DateTime class that extends Comparable that I am using to test and the sort seems to work but one out of every 20 or so runs a single value is out of place and when I use insertion sort on chunks of the array that are less than 8 the whole sort gets thrown out of whack.

In my partition method it kind of works when I move the pivot to the end and start my pointers at the start and end - 1. I want to move the pivot to end - 1 because the first and last are already sorted and start the pointers at first + 1 and end -2 but everything falls apart if I try that and I don't understand why.

So I have something that works now. It gets a little spastic when I don't use insertion sort on smaller sub arrays which bothers be but ill figure it out eventually. Thanks to ben j for pointing out about falling out of the array...that was causing the insertion sort issue. :)

My current code is below

    Comparable** partition(Comparable** from, Comparable** to)
{
    Comparable** pivot  = from + (to - from) / 2;
    SortFirstMiddleLast(from, pivot, to - 1);
    swap(*pivot, *to);
    pivot = to;
    ++from; to -= 2;
    while (from <= to)
    {
        while (**from <= **pivot && from <= to) ++from;
        while (**to   >= **pivot && from <= to) --to;
        if (from < to)
        {
            swap(*from, *to);
            ++from; --to;
        }
    }
    swap(*from, *pivot);
    return from;
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

所有深爱都是秘密 2024-11-10 06:53:10

从您向我们展示的代码以及您对问题所在的评论中，我唯一的猜测是 from 和 to 并不意味着您的想法。您的代码将 to - from 作为要排序的段的长度。如果这是准确的（而不仅仅是枢轴选择的近似值），则意味着 to 实际上指向要排序区域之外的元素。这是合理的，但是 swap(*pivot, *(to)) 会将枢轴交换到列表末尾。