排序--快速排序
排序--快速排序
提问于 2011-04-25 03:14:50
我们必须为我们自己的可比较基类做一个优化的快速排序。以我的生命来说，我不能让它工作。这个算法看起来很简单，但是我看不到我的代码能正常工作。我有一个DateTime类，它扩展了我用来测试的比较类，排序似乎可以工作，但是每运行20次左右，就会有一个值不合适，并且当我对小于8的数组块使用插入排序时，整个排序都会抛出乱码。
在我的分区方法中，当我将轴心移动到末尾，并在开始和结束- 1处开始指针时，它是有效的。我想将轴心移动到结束-1，因为第一个和最后一个已经排序，并从第一个+1和结束-2开始指针，但如果我尝试这样做，所有的东西都会散开，我不明白为什么。
因此，我现在有了一些可以工作的东西。当我不在较小的子数组上使用插入排序时，它会变得有点痉挛，这会让be感到困扰，但最终我会弄清楚的。感谢ben j指出，array...that的失效是导致插入排序问题的原因。:)
我当前的代码如下
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;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2011-04-25 03:28:39
从你向我们展示的代码和你对哪里出了问题的评论中，我唯一的猜测是from和to并不是你想的那样。您的代码将to - from作为要排序的段的长度。如果这是准确的(不仅仅是旋转选择的近似值)，那就意味着to实际上指向了要排序的区域之外的元素。这是合理的，但swap<Comparable*>(*pivot, *(to))会将轴心从列表的末尾调出。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5772639
复制相关文章
相似问题
腾讯云开发者
