java - 改变java排序算法

Question

在这里启动 Java 编码器。我想知道如何更改我的代码，以便它通过始终将最大值交换到第一个来对数组进行排序。示例输出应为:

[3,1,2,0][3,2,1,0]。

public class Sorting {

static void biggest(int[] arr, int start, int end) {
    for (start = 0; start < arr.length; start++) {
        for (end = start + 1; end < arr.length; end++) {
            if (arr[start] < arr[end]) {
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
                System.out.println(Arrays.toString(arr));

            }
        }
    }
}

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3};
    int temp = 0;
    for (int i = 0; i < 4; ++i) {
        biggest(arr, temp, 4 - 1);
        for (int j = 0; j < 4; ++j) {
        }
        ++temp;
    }
}

提前致谢， - Em

Answer 1

如果您只是希望排序成功，我建议利用 Java 内置的排序方法，然后按照建议反转列表 here :

Arrays.sort(arr);
ArrayUtils.reverse(arr); 

但听起来你的问题的精神是为此目的修改你的代码。这是我想出的解决方案:

import java.util.Arrays;

public class Sorting {

static void biggest(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(Arrays.toString(arr));
        int max, maxAt = i;
        for (int j = i; j < arr.length; j++) {
            maxAt = arr[j] > arr[maxAt] ? j : maxAt;
        }
        max = arr[maxAt];
        if (arr[i] < max) {
            arr[maxAt] = arr[i];
            arr[i] = max;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3};
    biggest(arr);
    System.out.println(Arrays.toString(arr));
}
}

首先，您有很多不需要的额外代码。在你的 main 中有一个循环是一个坏主意。这应该由辅助函数来处理。您还有很多冗余声明(例如 start 和 end)。您的辅助函数走在正确的轨道上，但由于您的主循环，您的时间复杂度为 0(n²)。消除它可以让我的时间复杂度为 O(logn)。撇开复杂性不谈，逻辑方面的关键区别在于内部循环:

for (end = start + 1; end < arr.length; end++) {
        if (arr[start] < arr[end]) {
            int temp = arr[end];
            arr[end] = arr[start];
            arr[start] = temp;

在此循环中，您将使用您发现的第一个更大的数组条目交换数组条目。这将导致不必要的早期切换(如 1 和 2)。这是我的解决方案:

for (int j = i; j < arr.length; j++) {
        maxAt = arr[j] > arr[maxAt] ? j : maxAt;
    }
    max = arr[maxAt];
    if (arr[i] < max) {
        arr[maxAt] = arr[i];
        arr[i] = max;
    }

主要区别在于我搜索我们正在交换的条目之后的最大值条目。这样，当我们继续遍历数组时，我们总是会提出下一个最大的。

祝你学习 Java 好运，希望这会有所帮助!