0

我已经为数组列表编写了一个快速排序，就目前而言，逻辑似乎是合理的。我遇到的问题是交换元素。似乎正在发生的事情不是交换元素，而是用要交换的元素替换现有元素。一个示例运行以 [happy, apples, eat, food] 之类的列表开始，在排序运行之后，它会出现 [happy, happy, happy, food]。我确信我的错误很简单，但我已经盯着它看太久了，需要重新审视它。到目前为止，这是我的代码。提前致谢！

String pivot = list.get(0); // Choose the first element as the pivot
      int low = first + 1; // Index for forward search
      int high = last; // Index for backward search

      while (high > low) 
      { // Search forward from left
          while (low <= high && list.get(low).compareTo(pivot) <= 0)
          {

              low++;
          }
      // Search backward from right
      while (low <= high && list.get(high).compareTo(pivot) > 0)
      {
          high--;
      }
      // Swap two elements in the list
      if (high > low) 
      {

          String temp = list.get(high);
          list.set(high,list.get(low));
          list.set(low,temp);

      }
    }
    while (high > first && list.get(high).compareTo(pivot) <= 0)
    {

        high--;
    }
    // Swap pivot with list[high]
    if (list.get(high).compareTo(pivot) < 0) 
    { 
        list.set(first, list.get(high));
        list.set(high,pivot);
        return high;
    }
    else 
    {
        return first;
    }
  }
4

2 回答 2

0

是的，我认为错误很简单。试试这个

String tempHigh = list.get(high);
String tempLow = list.get(low);
list.set(high, tempLow);
list.set(low, tempHigh);

因为在java中赋值是通过引用完成的。在您的代码中，您只是将高值设置为高位和低位。当你用 list[high] 交换 pivot 时也会发生同样的事情

于 2013-04-30T03:14:28.827 回答
0

问题（在修复要使用的枢轴选择之后list.get(first)）是

while (high > first && list.get(high).compareTo(pivot) <= 0)

此时，索引之前（包括）索引之前的所有元素high（按字典顺序）都小于或等于枢轴。因此

while (high > first && list.get(high).compareTo(pivot) <= 0) {

    high--;
}

可以简写为high = first。

这解释了第一个元素与

String pivot = list.get(0);

枢轴选择，因为在您的示例中，索引 0 处的元素是最大的，因此

if (list.get(high).compareTo(pivot) < 0) 
{ 
    list.set(first, list.get(high));
    list.set(high,pivot);
    return high;
}

分支被采取，list.set(first, list.get(high));什么都不做，因为high == first，然后list.set(high,pivot);将枢轴复制到索引high (== first)。

您在有问题的行中需要的是

if (list.get(high).compareTo(pivot) > 0) {
    --high;
}

如果在第一个分区循环之后索引high处的元素大于枢轴，则之前的元素小于或等于枢轴。否则，high是不大于枢轴的元素的最大索引。

于 2013-04-30T04:14:25.563 回答