java的归并排序怎么写呢
时间: 2023-09-06 16:04:01 浏览: 60
### 回答1:
归并排序是一种基于分治思想的排序算法,Java中的归并排序可以使用递归来实现。
以下是Java中的归并排序实现:
```java
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}
while (i <= mid) {
temp[k] = arr[i];
i++;
k++;
}
while (j <= right) {
temp[k] = arr[j];
j++;
k++;
}
for (int m = 0; m < temp.length; m++) {
arr[left + m] = temp[m];
}
}
```
其中,mergeSort方法接受一个待排序数组arr以及数组的左右边界left和right,递归地将数组分为左右两个部分,然后调用merge方法将左右两个部分合并起来。
merge方法接受一个待合并数组arr,以及数组的左中右三个位置,它会将左半部分和右半部分分别归并排序后,再将它们合并为一个有序数组。具体实现中,需要使用一个临时数组temp来保存排序后的结果。
### 回答2:
归并排序是一种常见的排序算法,它的主要思想是将待排序的序列分成若干个小的子序列,然后将这些子序列两两合并,最终得到一个有序的序列。
下面是Java中归并排序的实现:
```java
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = left + ((right - left) >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] helper = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
helper[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
helper[i++] = arr[p1++];
}
while (p2 <= right) {
helper[i++] = arr[p2++];
}
for (i = 0; i < helper.length; i++) {
arr[left + i] = helper[i];
}
}
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
mergeSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上是一个简单的归并排序的实现。在这个例子中,我们定义了一个`mergeSort`方法来对整个数组进行排序,同时还定义了`mergeSort`和`merge`两个私有方法来实现分治和合并操作。在`merge`方法中,我们创建了一个辅助数组`helper`来存储合并后的结果,然后使用双指针`p1`和`p2`分别指向左右两个子数组的起始位置,通过比较两个指针指向的元素大小将较小的元素放入辅助数组中,直到其中一个子序列遍历完。最后,将辅助数组中的元素拷贝回原数组的对应位置。通过不断地递归调用`mergeSort`方法和合并操作`merge`,最终实现了归并排序算法。
以上就是Java中归并排序的基本实现。实际应用中,我们通常会使用更加高效的算法以及优化手段来提升归并排序的性能。
### 回答3:
归并排序是一种基于分治思想的排序算法。它将待排序的数组不断地二分为两个子数组,直到子数组的长度为1。然后再将这些长度为1的子数组合并,直到最终得到有序的数组。
具体实现归并排序的步骤如下:
1. 首先编写一个合并函数merge,用于将两个有序数组合并为一个有序数组。该函数需要创建一个临时数组用于存放合并结果,并使用两个指针分别指向两个待合并的数组的起始位置。依次比较两个指针所指向的元素的大小,将较小的元素放入临时数组,同时移动指针。直到其中一个数组的所有元素都合并完毕,然后将剩下的数组的所有元素直接放入临时数组。最后将临时数组的内容复制回原数组的相应位置。
2. 编写归并排序函数mergeSort。该函数首先需要判断待排序数组的长度,如果数组长度小于等于1,则直接返回。否则,将数组二分为两个子数组,然后分别对两个子数组调用mergeSort函数进行递归排序。最后再调用merge函数将两个排好序的子数组进行合并。这样就完成了一次归并排序。
3. 在主函数中调用mergeSort函数,传入待排序数组作为参数即可完成对数组的归并排序。
通过以上步骤,即可实现对数组的归并排序。归并排序的时间复杂度为O(nlogn),是一种稳定的排序算法。