快速排序使用arraylist java

我已经写了一个阵列列表的快速排序，因为它的逻辑似乎是健全的。我遇到的问题是交换元素。似乎发生的事情不是交换元素，而是将现有元素替换为要交换的元素。一个示例运行从一个像[开心，苹果，吃，食物]这样的列表开始，在排序运行后，它会出现[快乐，开心，快乐，食物]。我相信我的错误很简单，但我一直在盯着它太久，需要新鲜的眼睛。这是我的代码到目前为止。提前致谢！快速排序使用arraylist java

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; 
    } 
    }

来源

2013-04-30 Justin Ertley

'String pivot = list.get（0）; //选择第一个元素作为pivot' < - 应该是'list.get（first）'。 – 2013-04-30 02:56:57

谢谢，我发布代码后发现，但它没有解决我遇到的问题。 – 2013-04-30 03:17:53

问题枢轴

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

在这一点上，之前（含）索引high所有元素（按照字典顺序）小于或等于枢轴。因此

而（高>第一& & list.get（高）.compareTo（枢转）< = 0） {

high--; 
}

可以缩写为high = first。

这在索引0解释的第一要素与

String pivot = list.get(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-30 04:14:25

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

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

因为在java中的赋值是通过引用完成的。在您的代码中，您只需将高价位设置为高位&低位。同样的事情会发生，当你（固定支点的选择使用list.get(first)）之后换用列表[高]

来源

2013-04-30 03:14:28 JavaKB

我试过这种方法，不幸的是，它并没有解决我的问题。我的问题可能比我原先想象的要大。 – 2013-04-30 03:31:08

快速排序使用arraylist java

回答

相关问题