2

我写了一个修改版本的选择排序，我考虑了一个数组的最小值和最大值，并将它们放在两端

算法是这样工作的

1. Find the minimum and the maximum value in the list.
2. Swap the minimum value with the value in the first position.
3. Swap the maximum value with the value in the last position.
4. Repeat the steps above for the remainder of the list 
(starting at the second position and ending at the second to 
 last position and narrowing the range of positions examined 
 from both ends of the array each time).

不幸的是，上面显示了具有重复值的数组的意外结果。

例如，

[9, 37, 12, 1, 13, 31, 5, 37, 36, 29, 19, 22, 20, 15, -1, 23]

被排序到

[-1, 1, 5, 9, 12, 13, 15, 19, 20, 22, 23, 29, 31, 37, 36, 37]

事实上，这里的主要问题是算法通常没有对数组后半部分的元素进行适当的排序，除了简单的重复。

这是我的伪代码

    int i=0;
    while(i<=(arr.length-i-1)) {
      int minIndex = i;
      int maxIndex=arr.length-i-1; 
      for (int j = i+1; j <=arr.length-i-1; j++) {

       if (arr[j] <=arr[minIndex]) {
         minIndex = j;      
         } 
       if(arr[j]>=arr[maxIndex]){
          maxIndex = j; 
         }
      }
      swap(arr, i, minIndex);
      swap(arr, (arr.length-i-1), maxIndex); 
    i++;
    }

编辑这是我代码的交换部分，它是唯一与算法交互的东西。我认为它不会有任何区别，但无论如何我都会包含它

 private static void swap(int[] arr, int oldIndex, int newIndex){

    int temp=arr[oldIndex];
    arr[oldIndex]=arr[newIndex];
    arr[newIndex]=temp;
 }
4

5 回答 5

3

当i恰好是maxIndex. 要解决这个问题，您需要添加：

swap(arr, i, minIndex);
if(i == maxIndex) {
     maxIndex = minIndex;
}
swap(arr, (arr.length-i-1), maxIndex);

看到它@work

于 2012-04-17T11:55:32.290 回答
2

好的，问题是最大值从迭代的最小位置开始的情况。考虑第二次通过问题数组的循环：

-1,37,12,1,13,31,5,23,36,29,19,22,20,15,9,37

i 为 1，len-i-1 为 14。循环后，maxindex 为 1，minIndex 为 3。

所以你交换 1 (i) 和 3 (minIndex)：

-1,1,12,37,13,31,5,23,36,29,19,22,20,15,9,37

然后是 14 (len-i-1) 和 1 (maxIndex)：

-1,9,12,37,13,31,5,23,36,29,19,22,20,15,1,37

哎呀。基本上，您需要同时进行两次交换。

EDIT Parallelism 在两个重叠交换的情况下并没有真正的帮助，因为每个交换都希望在其中一个数组槽中放置一个不同的值；你必须解决冲突。我认为@codaddict 的解决方案效果很好。

于 2012-04-17T11:49:36.183 回答
0

您在内部 for 循环的终止条件中有一个错误。

  for (int j = i+1; j <=arr.length-i-1; j++) {

那应该是 a <，而不是 a <=，出于同样的原因，你开始i+1而不是i。

作为文体建议，我还将值存储arr.length - i - 1在一个变量中，因为它在代码中出现了四次。

编辑：验证此错误不是问题的根源。

于 2012-04-17T11:26:23.497 回答
0

我认为您进行了太多交换 - 即无论您是否真的找到了新的最小值或最大值，您都在进行交换。此外，您不需要同时进行两个测试（最小和最大测试，因为您不能同时测试两者，除非在平凡的相等情况下，在这种情况下，它们的顺序无关紧要......）。

我认为以下是您算法的更好表示：

int arrayLength = arr.length;
for (int i=0; i<arrayLength; i++){
  for (int j=i+1; j<arrayLength; j++){
    int v = arr[j];
    if (v < arr[i]){
      swap(arr, i, j);
    } else if (v > arr[(arrayLength -1)]){
      swap(arr, (arrayLength -i-1), j);
    }
  }
}

但是，您实际上不需要对最大值进行测试以将它们交换到最后，因为当您通过数组进行顶级迭代时，这些都将被搜索最小值捕获 - 即

int arrayLength = arr.length;
for (int i=0; i<arrayLength; i++){
  for (int j=i+1; j<arrayLength; j++){
    int v = arr[j];
    if (v < arr[i]){
      swap(arr, i, j);
    } 
  }
}

会更有效率。

编辑：在查看了其他答案之后，这种类型的选择是对 Mark Reed 关于并行进行交换的回答——除此之外，我建议你按照你发现的需要进行交换。

于 2012-04-17T12:18:53.557 回答
-2

就像在评论中一样，您的第一次交换会做得很好，但您的第二次交换会产生问题。

在您的 maxindex 变量位于 i 的情况下，您正确放置了最小术语，但丢失了最大术语。这可以通过添加额外的检查来解决if(i==maxterm)，并通过正常进行第一次交换和第二次交换 maxterm 和 minterm 位置来处理这种特殊情况。你从 0 到遍历你的数组是没用的array.length-1

我建议，从 0 遍历到 (array.length-1)/2，因为你在两边排序。结束部分已经和开始部分一样排序，为什么要进行额外的迭代？我编写了一个完全相同的程序，其中包含我建议的更正，它还检查数字是否已经排序并立即终止循环。

于 2017-03-11T14:13:23.900 回答