用java写一个时间复杂度为n的排序
时间: 2024-05-09 21:21:50 浏览: 19
算法。
可以使用一些基于比较的排序算法,如快速排序、归并排序、堆排序等,这些算法的时间复杂度都是O(nlogn)。但是,如果我们只需要对一些整数进行排序,可以使用计数排序或基数排序等线性时间复杂度的算法,时间复杂度为O(n)。
以下是一个使用计数排序实现的例子:
```java
public static void countSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int min = arr[0];
int max = arr[0];
// 找到数组的最小值和最大值
for (int i = 1; i < arr.length; ++i) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
// 统计每个元素出现的次数
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; ++i) {
++count[arr[i] - min];
}
// 按顺序将元素依次放入数组中
int idx = 0;
for (int i = 0; i < count.length; ++i) {
for (int j = 0; j < count[i]; ++j) {
arr[idx++] = i + min;
}
}
}
```
该算法时间复杂度为O(n+max-min+1),其中n为数组长度,max和min为数组的最大值和最小值,也就是说,如果max和min的差不是很大,那么算法的时间复杂度就很接近O(n)了。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)