更改排序算法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的内置排序方法，然后按照这里的建议反转列表：

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

首先，您有很多不需要的额外代码。在你的主管道里有一个循环是个坏主意。这应该由helper函数处理。您还拥有许多冗余声明(如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好运，我希望这能有所帮助！