选择排序从两端增长有序范围 [英] Selection sort growing ordered ranges from both ends

问题描述

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

算法的工作原理如下

  1。查找列表中的最小值和最大值。 
 2.使用第一个位置的值交换最小值。 
 3.将最大值与最后一个位置的值进行交换。 
 4.重复上述步骤剩余的
（从第二个位置开始，到第二个到
最后一个位置，并缩小检查的位置范围
从每次阵列的两端）。 
  

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

例如，

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

解决方案

c $ c> i 恰好是 maxIndex 。要修复，您需要添加：

  swap（arr，i，minIndex）; 
 if（i == maxIndex）{
 maxIndex = minIndex; 
} 
 swap（arr，（arr.length-i-1），maxIndex）; 
  

请参阅@work

I have written a modified version of selection sort where I consider both a minimum and maximum of an array and place them at the two ends

The algorithm works like this

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).

Unfortunately the above is showing unexpected results for arrays having duplicates values.

For example,

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

was sorted to

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

In fact, the main issue here is that the algorithm in general is not doing proper sorting for the elements in the latter part of the array, besides simply with respect to duplicates.

Here is my pseudocode

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

EDIT This is the swap part of my code which is the only thing that interacts with the algorithm. I don't think it will make any difference but I'll include it anyway

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

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

解决方案

The problem happens when i happens to be the maxIndex. To fix that you need to add:

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

See it @work

这篇关于选择排序从两端增长有序范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！