java归并排序,deme样例
时间: 2023-09-13 18:05:16 浏览: 57
### 回答1:
好的,我可以回答这个问题。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, j = mid + 1, k = ;
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++];
}
for (int p = ; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
```
这段代码实现了归并排序的核心部分,你可以根据自己的需要进行调整和修改。
### 回答2:
归并排序是一种使用分治算法的排序方法。它将一个待排序的数组不断地分割成两个子数组,直到每个子数组都只有一个元素,然后将这些子数组合并成一个有序的数组。
下面是一个使用Java实现归并排序的代码样例:
```java
public class MergeSort {
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
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 main(String[] args) {
int[] arr = {9, 5, 1, 3, 8, 4, 2, 7, 6};
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
在上面的代码中,`merge()`方法用于合并两个已排序的子数组,`mergeSort()`方法用于递归地分割数组并调用`merge()`方法进行合并。在`main()`方法中,我们声明一个待排序的数组并调用`mergeSort()`方法进行排序。输出结果为排序后的数组:1 2 3 4 5 6 7 8 9。
### 回答3:
归并排序是一种经典的排序算法,它采用分治的思想,将一个大问题分解为若干小问题来解决,最后将结果合并得到有序的序列。
以下是一个使用Java实现的归并排序的示例:
```java
public class MergeSort {
public static void main(String[] args) {
int[] nums = {8, 5, 2, 9, 5, 6, 3};
mergeSort(nums, 0, nums.length - 1);
for (int num : nums) {
System.out.print(num + " ");
}
}
public static void mergeSort(int[] nums, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(nums, left, mid); // 对左半部分进行归并排序
mergeSort(nums, mid + 1, right); // 对右半部分进行归并排序
merge(nums, left, mid, right); // 合并两个有序子数组
}
}
public static void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (int m = 0; m < temp.length; m++) {
nums[left + m] = temp[m];
}
}
}
```
在这个示例中,我们先定义了一个`mergeSort`方法用于实现归并排序。它接受一个整型数组`nums`,以及需要排序的左边界`left`和右边界`right`。在每一次递归调用中,我们将数组划分为左右两个部分并分别进行归并排序,然后调用`merge`方法将两个有序子数组合并为一个有序的数组。
`merge`方法用于合并两个有序子数组。我们先创建一个临时数组`temp`来保存合并后的结果。然后使用三个指针`i`、`j`和`k`来遍历两个有序子数组和临时数组。比较`nums[i]`和`nums[j]`的大小,将较小的元素放入临时数组,并将对应的指针向后移动一位。最后,将剩下的未合并的元素依次放入临时数组末尾。最后,将临时数组的元素拷贝回原数组的对应位置,完成合并过程。
在`main`方法中,我们定义了一个示例数组`nums`,并调用`mergeSort`方法进行归并排序。最后,输出排序后的数组即可。
该示例即为使用Java实现的归并排序的简单样例。