快速排序不起作用

Question

这是我的快速排序方法的所有代码，它适用于一组 21 个数字，但不适用于我的真实数据集，大约 100000。我不知道出了什么问题，我已经摆弄了两个小时，它即将到期！任何帮助将非常受欢迎

public static void hybridQuicksort( int[] a, int start, int end )
{
    final int MIN = 13;
    if ( end - start >= MIN )
    {
        int pivot = findPivot( a, start, end );
        pivot = partition ( a, start, end, pivot );
        hybridQuicksort( a, start, pivot - 1 );
        hybridQuicksort( a, pivot + 1, end);
    }
    else
    {
        insertionSort( a, start, end );
    }
}

//partitions the array based on the pivot
public static int partition( int[] a, int start, int end, int pivot )
{
    int up = start + 1;
    int down = end;

    while ( up <= down )
    {

        while ( a[up] <= pivot)
            up++;

        while ( a[down] > pivot)
            down--;

        if ( up <= down )
            swap( a, up, down );
    }

    swap( a, start, down );

    return up;
}

//finds the first, middle, middle of first and middle, middle of middle and last
//and last numbers and sets their median as the pivot
public static int findPivot( int[] a, int start, int end )
{
    //swap the 4 numbers to the start of the array, leaving the first as is
    swap( a, start + 1, end - 1 );
    swap( a, start + 2, (start + end) / 2);
    swap( a, start + 3, end / 4);
    swap( a, start + 4, (end / 2) + (end / 4) );

    //sort the 5 numbers
    insertionSort( a, 0, 5 );

    //swap the median to the front, that's the pivot
    swap( a, start, start + 2 );
    //return the pivot
    return a[start];
}

Answer 1

假设：

• a 包含 10'000 个样本，
• 开始为 500

• 结束为 1000

  //将4个数字交换到数组的开头，第一个数字保持原样
  交换（a，开始+1，结束-1）；
  交换（a，开始+ 2，结束/ 2）；
  交换（a，开始+ 3，结束/ 4）；
  交换（a，开始+ 4，（结束/ 2）+（结束/ 4））；
  

end/4 是 250

.. 您正在交换排序子集外部的值。

Answer 2

这看起来不像是家​​庭作业问题。如果这是一个家庭作业问题，作者会写大约七到十行代码，并附上有效性证明，然后将其提交。这家伙想表现得花里胡哨，结果却在他背后咬了一口。您可以通过他对所谓的“小”间隔进行插入排序的方式来判断。 （提示：阈值间隔大小超过测试数据大小的一半。如果您想很好地测试算法，请给算法一些递归空间。）其次，他正在做额外的工作来找到理想的枢轴。这种复杂性是有代价的。

这是一个工作中的业余爱好者。他需要的不仅仅是一个答案。他需要一种解决难题的方法。快速排序正是这种教育的工具。

这是我的方法。

诀窍是将快速排序编写为快速排序，让它工作，然后担心花哨的特殊技巧。消除小区间插入排序的噪音。只需假设任何大小为零或一的间隔已经排序（这是您的基本情况），然后使用间隔的左端作为枢轴（如经典的原始快速排序）来使分区代码工作，您可能会考虑在一次分区之后打印数据结果，以此来证明它有效。您将通过这种方式培养测试技能。不管怎样，一旦你有了一个有效的快速排序，那么你就可以做一些事情，比如将枢轴选择单独放入一个函数中并进行实现。

祝你好运，享受你的项目。但不要忘记：我们需要计时，尤其是与标准库中的排序例程进行时间比较！