springboot 用for 对一个数组排序,要求时间复杂度低和空间复杂度低,最后输出排好序得数组
时间: 2024-03-11 13:51:10 浏览: 86
好的,我来给你一个基于冒泡排序算法的实现,它的时间复杂度为O(n^2),空间复杂度为O(1),同时还会输出排好序的数组。
```java
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
boolean flag = true;
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if (flag) { // 如果一趟下来没有交换,则说明已经有序,可以直接退出
break;
}
}
System.out.println(Arrays.toString(arr));
}
```
代码中的bubbleSort方法接收一个int数组作为参数,它实现了冒泡排序算法。在冒泡排序中,我们将相邻的两个元素进行比较,如果前面的元素比后面的元素大,则交换它们的位置。通过这样的比较和交换,每一趟冒泡都可以将一个元素放到它应该在的位置上。
代码中的两个for循环分别表示了外层循环和内层循环。外层循环控制了冒泡的次数,因为每一趟冒泡都可以将一个元素放到它应该在的位置上,所以我们只需要进行n-1次冒泡就可以将n个元素排序完成。内层循环控制了每一趟冒泡的比较和交换。
注意到我们在内层循环中设置了一个flag变量,用来记录这一趟冒泡是否进行了交换。如果没有进行交换,说明已经有序,可以直接退出循环,这样可以减少不必要的比较和交换,提高性能。
最后,我们在方法的最后使用Arrays.toString()方法将排好序的数组输出,方便查看结果。
阅读全文