修改后的选择排序，选择最大的数字

Question

我正在尝试编写一个修改后的选择排序，它选择最大的数字并将其放置在列表的末尾。我遇到了问题。该代码对列表进行了某种排序，但并不完美。这是我运行代码后的结果： 选择排序前：[2,8,7,1,3,5,9,4,6] 选择排序后：[1, 2, 8, 7, 3, 4, 5, 9, 6]

这是我的代码：

public static int[] sort(int[] list) {
int i, j, maxNum, maxInde, temp = 0;
    for (i = list.length-1; i >= 0; i--) {
        maxNum = list[i];
        maxInde = i;
        for (j = i; j < list.length; j++) {
            if (list[j] < maxNum) {
                maxNum = list[j];
                maxInde = j;
            }
        }
        if (maxNum < list[i]) {
            temp = list[i];
            list[i] = list[maxInde];
            list[maxInde] = temp;
        }
    }
    return list;
}  

我不知道问题出在哪里。

Answer 1

该算法在概念上存在缺陷，因为您从

n-1

向下扫描数组到

0

，并在每次迭代时从子数组

a[n-1,...,i]

中选择最大元素。该子数组应该始终被排序（并且应该由数组的

n-i

最大元素组成）——这类似于经典选择排序的循环不变式——以及要插入当前位置的最大元素应该来自另一个子数组，即

a[i,...,0]

。

另外，正如评论中提到的，不需要返回数组，因为算法可以修改它。

Answer 2

这是固定版本：

int i, j, maxNum, maxInde, temp = 0;
for (i = list.length-1; i >= 0; i--) {
// you start iterating from the end of the list 
// which means that the elements between i and the end of the list are sorted
    maxNum = list[i];
    maxInde = i;
    for (j = 0; j < i; j++) { 
    // you have to iterate through the nonsorted elements
        if (list[j] > maxNum) {
            maxNum = list[j];
            maxInde = j;
        }
    }
    if (maxNum > list[i]) {
    // if you found an element that is bigger then the current element
    // then it should be set as the current element
        temp = list[i];
        list[i] = list[maxInde];
        list[maxInde] = temp;
    }
}

Answer 3

public static void sortArray(int[] a) {

    //find max value in this array
    for (int i = 0; i < a. length; i++) {
        int max=a[0];
        int index=0;
        for (int j=0; j<a. length-i; j++) {
            if (a[j] >max) {
                max=a[j];
                index=j;
            }
        }
        //change the index
        a[index]=a[a.length-(i+1)];
        a[a.length-(i+1)]=max; //max value change the last element
        
    }
}
public static void main (String args[]) {
    int [] a= {91,13,53,64,48,49,99,35,65,38,62,72};
    System.Out.Println (Arrays.toString (ar));
    sortArray(ar);
    System.Out.Println (Arrays.toString (ar));
}

}

Answer 4

public static int[] selectionSortWithMax(int[] items) {
    int size = items.length;
    int maxIndex;
    for (int i = size - 1; i >= 0; i--) {
      maxIndex = i;
      for (int j = i; j >= 0; j--) {
        if (items[maxIndex] < items[j]) {
          maxIndex = j;
        }
      }
      int temp = items[i];
      items[i] = items[maxIndex];
      items[maxIndex] = temp;
    }
    return items;
  }