代码之家 › 专栏 › 技术社区 › Red Eyez

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

selection-sort sorting java

Red Eyez · 技术社区 · 6 年前

我想实现一个选择排序方法,它接受一个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

2 回复 | 直到 6 年前

Leo Aso 6 年前

你原来的算法是错误的。首先是 if 块应与 minPosition 和 maxPosition ,不是 i . 第二,如果你选择两个最小值和最大值,那么你的内部for循环应该在 a.length - i ,不是 a.length (从顶部开始) 元素也被排序)。这两种方法都提供了升序算法。

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

Gregory Gan 6 年前

首先,让我们查找代码中的问题。有几个,这在编程中经常发生。

swap(a,minPosition,i) ,然后尝试将最大值放在末尾,这不是您想要的:您想要将最大值放在开头。
你的 n 永远不会修改,所以你会继续打印 0 .

样品溶液

现在让我们来看看一些有用的东西。我不太清楚你的想法选择排序看起来像,但我想应该是这样的:

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