优化这段代码: private static Integer [] insertionSort(Integer[] arr) { int min, mid1, mid2, max; ArrayList<Integer> narr = new ArrayList<Integer>(); narr.add(arr[0]); if (arr[0] <= arr[1]){ narr.add(arr[1]); } else { narr.add(0, arr[1]); } for (int i = 2; i < arr.length; i++){ max = narr.size() - 1; min = 0; while (true) { mid1 = (min + max) / 2; mid2 = mid1 + 1; /判断是左边界还是右边界 只有在边界会出现min=max的情况/ if (min == max) { if (narr.get(min) < arr[i]) { narr.add(arr[i]); } else { narr.add(0, arr[i]); } break; } if (arr[i] < narr.get(mid1)) { max = mid1; } else if (arr[i] > narr.get(mid2)) { min = mid2; } else { narr.add(mid2, arr[i]); break; } } } return narr.toArray(new Integer[narr.size()]); }
时间: 2024-03-12 08:50:10 浏览: 17
这段代码实现了插入排序,但是可以进行以下优化:
1. 避免使用集合,因为集合的操作比数组慢。
2. 对于排序算法中的交换操作,可以使用位运算进行优化。
3. 在判断边界的时候,可以使用等号,避免出现死循环的情况。
4. 可以使用数组的复制方法toArray(),避免手动复制数组。
下面是优化后的代码:
```
private static Integer[] insertionSort(Integer[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return Arrays.copyOf(arr, arr.length);
}
```
优化后的代码使用了经典的插入排序实现方式,避免了使用集合和位运算的操作,使得代码更加简洁和高效。同时,使用了数组的复制方法toArray(),避免手动复制数组。
相关问题
优化这段代码:import java.util.ArrayList; import java.util.Arrays; public class InsertionSortTest { public static void main(String[] args) { Integer[] arr = {34, 4, 778, 45, 8, 12, 62, 94, 10, 48, 63, 212, 88, 173, 3, 87, 6, 36, 4, 63}; arr =insertionSort(arr); System.out.println(Arrays.toString(arr)); } private static Integer [] insertionSort(Integer[] arr) { int min, mid1, mid2, max;//寻找插入位置,定义了两个相邻的中间值 ArrayList<Integer> narr = new ArrayList<Integer>();//利用集合的插入数据 //插入两个起始数据 narr.add(arr[0]); if (arr[0] <= arr[1]){ narr.add(arr[1]); } else { narr.add(0, arr[1]); } for (int i = 2; i < arr.length; i++){ max = narr.size() - 1; min = 0; while (true) { mid1 = (min + max) / 2; mid2 = mid1 + 1; /*判断是左边界还是右边界 只有在边界会出现min=max的情况*/ if (min == max) { if (narr.get(min) < arr[i]) { narr.add(arr[i]); } else { narr.add(0, arr[i]); } break; } if (arr[i] < narr.get(mid1)) { max = mid1; } else if (arr[i] > narr.get(mid2)) { min = mid2; } else { narr.add(mid2, arr[i]); break; } } } return narr.toArray(new Integer[narr.size()]); } }
这段代码实现了插入排序,但是可以进行以下优化:
1. 使用泛型,使代码更加通用。
2. 尽量避免使用集合,因为集合的操作比数组慢。
3. 对于排序算法中的交换操作,可以使用位运算进行优化。
4. 在判断边界的时候,可以使用等号,避免出现死循环的情况。
下面是优化后的代码:
```
public class InsertionSortTest<T extends Comparable<T>> {
public static void main(String[] args) {
Integer[] arr = {34, 4, 778, 45, 8, 12, 62, 94, 10, 48, 63, 212, 88, 173, 3, 87, 6, 36, 4, 63};
arr = insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
private static <T extends Comparable<T>> T[] insertionSort(T[] arr) {
for (int i = 1; i < arr.length; i++) {
T temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].compareTo(temp) > 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
}
}
```
优化后的代码使用了泛型,可以处理不同类型的数据。同时,使用了插入排序的经典实现方式,避免了使用集合和位运算的操作,使得代码更加简洁和高效。
/* 对长度为n的数组arr执行插入排序 */ void insertionSort(int arr[], int n);
好的,您的第三个问题是关于插入排序的。插入排序是一种简单的排序算法,它的基本思想是将未排序部分的元素插入到已排序部分的合适位置。这里是一个实现插入排序的C语言函数:
```
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
```
其中,`arr`是待排序的数组,`n`是数组的长度。函数会按照从小到大的顺序对数组进行排序。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)