Java 中的归并排序程序

Java 中的归并排序程序是使用最广泛、最高效的算法之一。合并排序基于分而治之技术，涉及将给定问题划分为多个子问题并独立解决每个子问题。当子问题解决后，我们将它们的结果结合起来得到问题的最终解决方案。合并排序算法可以使用递归来实现，因为它涉及到子问题而不是主要问题。

归并排序是如何工作的？

让我们考虑一个需要使用合并排序算法进行排序的未排序数组。以下是对包含值 18、8、4、13、10、12、7 和 11 的数组进行排序所涉及的步骤：

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

• 第一步涉及找到一个主元元素，在此基础上我们的输入数组将被划分为子数组。
• 让我们考虑选择元素 13 作为主元；因此，原始数组将被分为两个子数组。第一个子数组将包含 18, 8, 4, 13，第二个子数组将包含其余元素 10, 12, 7, 11。
• 将步骤 2 中获得的子数组按照步骤 1 进一步细分，如此继续。
• 一旦主数组被划分为具有单个元素的子数组，我们就开始再次合并这些子数组，以使合并后的元素按排序顺序排列。
• 以下是实际分而治之的工作原理：

Java 中的归并排序程序

下面是一个代码示例，展示了 java 中合并排序的实现：

代码：

package com.edubca.sorting;
public class MergeSort {
private int[] array;
private int[] tempMergedArr;
private int length;
public static void main(String a[]){
int[] inputArr = {18, 8, 4, 13, 10, 12, 7, 11};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr){
System.out.print(i + " ");
}
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int[length];
performMergeSort(0, length - 1);
}
private void performMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
}
}
private void mergeData (int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergedArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergedArr[i] <= tempMergedArr[j]) {
array[k] = tempMergedArr[i];
i++;
} else {
array[k] = tempMergedArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergedArr[i];
k++;
i++;
}
}
}

上面的代码将生成一个排序数组作为输出。

输出：

我们什么时候应该使用归并排序？

归并排序可以用在以下场景：

• 当要排序的数据结构不支持随机访问时，合并排序会很有帮助且高效。
• 当需要高水平的并行性时，可以使用归并排序，因为可以使用并行运行的多个进程独立解决不同的子问题。
• 使用链表时合并排序速度更快，因为在合并列表时可以轻松更改指针。
• 合并排序可以被认为是一种稳定排序，这意味着数组中的相同元素保持其相对于彼此的原始位置。如果需要高稳定性，可以采用归并排序。 

归并排序的复杂度分析

以下几点分析归并排序的复杂度：

• 归并排序是一种递归算法，在所有三种情况（最差、最佳和平均）下，其时间复杂度均为 O(n*log n)，因为归并排序将数组分成相等的两半，并花费线性时间来合并它们.
• 归并排序的空间复杂度为 O(n)，因为它采用递归方法。因此，合并排序可以被认为是一种快速、空间和时间高效的算法。

合并排序与其他算法的比较

以下几点将合并排序与其他算法进行比较：

• 堆排序与归并排序具有相同的时间复杂度，但它只需要 O(1) 辅助空间，而不是归并排序的 O(n)。因此，堆排序比合并排序更节省空间。
• 对于基于 RAM 的数组进行排序，快速排序实现通常优于合并排序。
• 在使用链表时，合并排序优于快速排序和堆排序算法，因为指针可以轻松更改。

结论-Java 中的归并排序程序

文章的结论是，合并排序是算法中需要理解的一个重要概念。

以上是Java 中的归并排序程序的详细内容。更多信息请关注PHP中文网其他相关文章！