0

我正在尝试在 java 中编写一个快速排序程序。这是我的分区函数

int partition(int[] array, int start, int end) 
{
    int last = end - 1;
    int first = start;
    int pivot = array[start];
    while (first < last)
    {
        while (first < last && pivot <= array[last])
            last = last - 1;
        array[first] = array[last];
        while (first < last && pivot > array[first])
            first = first + 1;
        array[last] = array[first];
    }
    array[first] = pivot;
    return first;
}

这就是我的快速排序功能

void quickSort(int array[], int start, int end) {
      int index = partition(array, start, end);
      if (start < index - 1)
            quickSort(array, start, end - 1);
      if (index < end)
            quickSort(array, index, end);}

但是当我在 Junit 中测试代码时，它给了我错误。我需要更改快速排序或分区功能。我能用它做什么。

4

3 回答 3

1

这里：

 if (start < index - 1)
                quickSort(array, start, end - 1);

为什么从 start 到 end-1 为较低的分区调用 quickSort？不应该是：

  if (start < index - 1)
                    quickSort(array, start, index - 1);

而上半部分是从index+1到end。

此外，最好在分区之前检查这样的限制并删除您的 if 语句：

 if (end <= start) { return; }
于 2013-11-05T10:43:38.820 回答
0

“quickSort（数组，索引，结束）行上的堆栈溢出错误；

当数组足够大时，recusion 调用太多次相同的函数溢出堆栈。

代替递归将索引对放在堆栈中并为顶部对调用 quickSort()。

void quickSort(int array[], int start, int end) {
  int index = partition(array, start, end);
  if (start < index - 1)
//        quickSort(array, start, end - 1);
        push(start, end - 1);
  if (index < end)
//        quickSort(array, index, end);}
        push(index, end);

while(stack is not empty) {
    //get next pair and call quickSort
}
于 2013-11-05T11:25:11.527 回答
0

对我来说，编写上述函数似乎不太直观。以我刚刚编写（并测试）的这个示例代码为例，看看您是否可以理解它并使用它来帮助您完成代码。注意：这与您的略有不同，因为它随机选择一个支点。 

void quicksort(int[] nums)
{
    if (nums.length > 1)
    {
          quicksort(nums, 0, nums.length);
    }
}

//[left,right)
private void quicksort(int[] nums, int left, int right)
{   
    if (left < right - 1)
    {
        int position = left;
        int pivot = pickPivot(left, right);

        if (pivot != right - 1)
            swap(nums, pivot, right-1);

        for (int i = left; i < right - 1; i++)
        {
            if (nums[i] <= nums[right-1])
            {
                swap(nums, position, i);
                position++;
            }
        }

        swap(nums, position, right-1);
        quicksort(nums, left, position);
        quicksort(nums, position + 1, right);
    }
}

//[left,right)
private int pickPivot(int left, int right)
{
     return rand.nextInt(right-left) + left; // rand is a Random object
}

private void swap(int[] nums, int start, int end)
{
    int temp = nums[end];
    nums[end] = nums[start];
    nums[start] = temp;
}

正如其他人所说，调试递归函数可能很困难。如果您无法从这里弄清楚，我建议使用调试器。Eclipse 的调试器非常易于使用并且非常有用。这可能令人沮丧且难以弄清楚，但这个过程是每个程序员（应该并且）必须经历的过程。

一旦你认为你已经弄清楚了，使用类似于这个的测试函数来测试它（我最初会从一个较小size的开始，以防出现错误，这样会更容易调试）：

void testQuickSort()
{
    for(int i = 0; i < 1000; i++)
    {
        int size = rand.nextInt(100)+1;
        int[] nums = new int[size];

        for (int j = 0; j < size; j++)
        {
            nums[j] = rand.nextInt(10);

            if (rand.nextBoolean())
            {
                nums[j] *= -1;
            }
        }

        quicksort(nums);
        assert sorted(nums) == true;
    }
}  

private boolean sorted(int[] array)
{
    for (int i = 0; i < array.length-1; i++)
    {
        if (array[i] > array[i+1])
            return false;
    }

    return true;
}
于 2013-11-05T11:13:25.447 回答