帮我用JAVA写一段归并排序的代码,并给出时间复杂度和空间复杂度
时间: 2024-10-01 20:09:14 浏览: 9
当然可以,归并排序是一种稳定的分治算法,它将数组分为两半,分别对它们进行排序,然后合并这两个已排序的部分。以下是用Java编写的归并排序示例:
```java
public class MergeSort {
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 分治策略:递归地排序左半部分和右半部分
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并两个已排序的部分
merge(arr, left, mid, right);
}
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1]; // 堆辅助数组
int i = left, j = mid + 1, k = 0;
// 将较小的元素逐步放入temp数组,然后复制回原数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 如果左半部分还有剩余元素,直接复制过去
while (i <= mid) {
temp[k++] = arr[i++];
}
// 如果右半部分还有剩余元素,直接复制过去
while (j <= right) {
temp[k++] = arr[j++];
}
// 将temp数组的内容复制回原数组
for (i = left; i <= right; i++) {
arr[i] = temp[i - left];
}
}
public static void main(String[] args) {
int[] arr = {9, 7, 5, 11, 12, 2, 14, 3};
MergeSort sort = new MergeSort();
sort.mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
```
**时间复杂度**: 归并排序的时间复杂度为O(n log n),其中n是数组长度。这是因为每个元素都会经过log n层递归处理,每层需要O(n)的时间。
**空间复杂度**: 空间复杂度为O(n),因为归并排序创建了一个临时数组来存储中间结果。当递归到最底层时,需要额外的空间来存储所有的元素。