如何在Java中实现降序选择排序? [英] how to implement a descending selection sort in java?

问题描述

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

i want to implement a selection sort method that takes an array of ints and sorts it in a descending order. however, the trick is to keep the original selection sort method unchanged but instead using simple arithmetic operations and without adding extra loops to swap the elements after the array finished sorting. this is my code and the idea is to store the position of the maximum value and the minimum value in local variables and swap them with the corresponding position after the inner loop finishes iteration. i even tried using a only one variable to find the lowest value and put it at the end of the array but i failed and i am getting the wrong results and i need help spotting the error. here is my code

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

here is the output of the program so far -3 8 2 9 13 5 4 6 3 1 7 0

推荐答案

您原来的算法是错误的.首先，if块应与minPosition和maxPosition而不是i进行比较.其次，如果您同时选择了最小值和最大值，那么您的内部for循环应该停在a.length - i而不是a.length(因为顶部的i元素也已排序).两者都可以为您提供升序算法.

Your original algorithm is wrong. Firstly, the if blocks should compare to minPosition and maxPosition, not i. Secondly, if you are selecting both minimum and maximum, then your inner for loop should stop at a.length - i, not a.length (since the top i elements are also sorted). Doing both gives you this as the ascending order algorithm.

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

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

To switch to descending order, simply add one line.

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

这篇关于如何在Java中实现降序选择排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！