如何在java中实现降序选择排序？

Question

我想实现一个选择排序方法，它接受一个整数数组并按降序对其进行排序。然而，诀窍是保持原始选择排序方法不变，而是使用简单的算术运算，并且在数组完成排序后不添加额外的循环来交换元素。这是我的代码，想法是将最大值和最小值的位置存储在局部变量中，并在内循环完成迭代后将它们与相应的位置交换。我什至尝试只使用一个变量来找到最小值并将其放在数组的末尾，但我失败了，我得到了错误的结果，我需要帮助发现错误。这是我的代码

public static void newSortMethod(int[]a){

    for(int i = 0; i < a.length-1; i++){

        int maxPosition=i;

        int minPosition=i;

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

            if(a[j] < a[minPosition]){

                minPosition = j;

            }

            if(a[j] > a[maxPosition]){

                maxPosition = j;

            }

        }

        swap(a,maxPosition,i);

        swap(a,minPosition,a.length-i-1);

    }

    System.out.println();

}

public static void swap(int[]a, int i, int j){

    int temp = a[i];

    a[i] = a[j];

    a[j] = temp;

}

public static void main(String[] args) {

    int[] a = {2,6,3,9,5,4,8,7,0,13,-3,1};

    newSortMethod(a);

}

这是到目前为止程序的输出 -3 8 2 9 13 5 4 6 3 1 7 0

Answer 1

你原来的算法是错误的。首先，if块应该与minPosition和进行比较，而maxPosition不是i。其次，如果您同时选择最小值和最大值，那么您的内部 for 循环应该停止在a.length - i, 不是a.length（因为顶部i元素也已排序）。两者都做给你这个作为升序算法。public static void newSortMethod(int[]a){&nbsp; &nbsp; for(int i = 0; i < a.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; int maxPosition=i;&nbsp; &nbsp; &nbsp; &nbsp; int minPosition=i;&nbsp; &nbsp; &nbsp; &nbsp; for(int j = i+1; j < a.length - i; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(a[j] < a[minPosition]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minPosition = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(a[j] > a[maxPosition]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxPosition = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; swap(a,maxPosition,i);&nbsp; &nbsp; &nbsp; &nbsp; swap(a,minPosition,a.length-i-1);&nbsp; &nbsp; }}要切换到降序，只需添加一行。public static void newSortMethod(int[]a){&nbsp; &nbsp; for(int i = 0; i < a.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; int maxPosition=i;&nbsp; &nbsp; &nbsp; &nbsp; int minPosition=i;&nbsp; &nbsp; &nbsp; &nbsp; for(int j = i+1; j < a.length - i; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(a[j] < a[minPosition]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minPosition = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(a[j] > a[maxPosition]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxPosition = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; swap(a,minPosition,maxPosition); // <-- this line&nbsp; &nbsp; &nbsp; &nbsp; swap(a,maxPosition,i);&nbsp; &nbsp; &nbsp; &nbsp; swap(a,minPosition,a.length-i-1);&nbsp; &nbsp; }}

Answer 2

错误首先，让我们查找代码中的问题。有一些，这在编程中经常发生。您的代码仍在尝试使用 进行升序排序swap(a,minPosition,i)，然后尝试将最大值放在最后，这不是您想要的：您想将最大值放在开头。您n永远不会修改，因此您将继续打印0.样品溶液现在让我们看看一些有用的东西。我不完全确定您的升序选择排序是什么样的，但我想它应该是这样的：public static void ascendingSortMethod(int[]a){&nbsp; &nbsp; int n = 0; // this is only to count how many times the swap method was called&nbsp; &nbsp; for(int i = 0; i < a.length-1; i++){&nbsp; &nbsp; &nbsp; &nbsp; int minPosition = i;&nbsp; &nbsp; &nbsp; &nbsp; for(int j = i+1; j < a.length; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(a[j] < a[minPosition]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minPosition = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if(minPosition != i){ // check whether swap is necessary&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; swap(a,minPosition,i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n ++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(n);}要使其按降序排序，只需切换比较运算符（minPosition为了清楚起见，可能还切换标识符）。public static void newSortMethod(int[]a){&nbsp; &nbsp; int n = 0; // this is only to count how many times the swap method was called&nbsp; &nbsp; for(int i = 0; i < a.length-1; i++){&nbsp; &nbsp; &nbsp; &nbsp; int maxPosition = i;&nbsp; &nbsp; &nbsp; &nbsp; for(int j = i+1; j < a.length; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(a[j] > a[maxPosition]){ // switched comparison operator&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxPosition = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if(maxPosition != i){ // check whether swap is necessary&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; swap(a,maxPosition,i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n ++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(n);}