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

Question

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

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){
    for(int i = 0; i < a.length; i++){
        int maxPosition=i;
        int minPosition=i;
        for(int j = i+1; j < a.length - i; 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);
    }
}

要切换到降序，只需添加一行。

public static void newSortMethod(int[]a){
    for(int i = 0; i < a.length; i++){
        int maxPosition=i;
        int minPosition=i;
        for(int j = i+1; j < a.length - i; j++){
            if(a[j] < a[minPosition]){
                minPosition = j;
            }
            if(a[j] > a[maxPosition]){
                maxPosition = j;
            }
        }
        swap(a,minPosition,maxPosition); // <-- this line
        swap(a,maxPosition,i);
        swap(a,minPosition,a.length-i-1);
    }
}

Answer 2

Errors

首先，让我们在代码中查找问题。有一些，在编程中发生了很多。

• 您的代码仍在尝试使用swap(a,minPosition,i)进行升序排序，然后尝试将最大值放在最后，这不是您想要的：您希望在开头放置最大值。
• 你的n永远不会被修改，所以你将继续打印0。

Sample solution

现在让我们看看有用的东西。我不完全确定你的升序选择是什么样的，但我想它应该是这样的：

public static void ascendingSortMethod(int[]a){
    int n = 0; // this is only to count how many times the swap method was called
    for(int i = 0; i < a.length-1; i++){
        int minPosition = i;
        for(int j = i+1; j < a.length; j++){
            if(a[j] < a[minPosition]){
                minPosition = j;
            }
        }
        if(minPosition != i){ // check whether swap is necessary
            swap(a,minPosition,i);
            n ++;
        }
    }
    System.out.println(n);
}

要使其按降序排序，只需切换比较运算符（为清晰起见，可能还需要minPosition标识符）。

public static void newSortMethod(int[]a){
    int n = 0; // this is only to count how many times the swap method was called
    for(int i = 0; i < a.length-1; i++){
        int maxPosition = i;
        for(int j = i+1; j < a.length; j++){
            if(a[j] > a[maxPosition]){ // switched comparison operator
                maxPosition = j;
            }
        }
        if(maxPosition != i){ // check whether swap is necessary
            swap(a,maxPosition,i);
            n ++;
        }
    }
    System.out.println(n);
}