package algorithm.sort;
/**
* 合并(归并)排序:按照分治模式,操作如下:
* 分解:将n个元素分成各含n/2个元素的子序列
* 解决:用合并排序法对两个子序列递归排序
* 合并:合并两个已经排序的子序列已得到排序结果
* @author Administrator
*/
public class MergeSort {
/**
* 合并排序的关键在于合并两个已经排好序的子序列
* a[from, mid],a[mid+a, end]已排好序,合并成已排序的数组代替a[from, end]
* @param a
* @param from
* @param end
* @param mid
*/
//方法一:在过程中利用最大值作为哨兵值,来避免检查每个子序列是否为空
//一旦两个子序列都出现这个哨兵值,说明所有的值都已经合并,复制回数组a
public void merge1(int[] a, int from, int mid, int end) {
//左右数组,且每个数组长度+1,为了存放哨兵值
int nl = mid - from + 1;
int nr = end - mid;
int[] left = new int[nl + 1];
int[] right = new int[nr + 1];
System.arraycopy(a, from, left, 0, nl);
System.arraycopy(a, mid+1, right, 0, nr);
//哨兵值
left[nl] = Integer.MAX_VALUE;
right[nr] = Integer.MAX_VALUE;
int i = 0; //控制左边数组
int j = 0; //控制右边数组
//从左右两个临时数组中各取一个数比较,将较小的一个数复制回数组
for (int k = from; k <= end; k++) {
if (left[i] <= right[j]) {
//哨兵值在这里得到体现,如果其中一个复制完,就会一直复制另外一个
a[k] = left[i];
i++; //接着下一个
} else {
a[k] = right[j];
j++;
}
}
}
//方法二:不使用哨兵值,一旦其中的一个子序列所有元素都被复制回数组a,就立刻停止
//再将另外一个子序列中剩余的元素复制回数组a即可
public void merge2(int[] a, int from, int mid, int end) {
//左右数组
int nl = mid - from + 1;
int nr = end - mid;
int[] left = new int[nl];
int[] right = new int[nr];
System.arraycopy(a, from, left, 0, nl);
System.arraycopy(a, mid+1, right, 0, nr);
int i=0, j=0, k=from;
//一旦其中一个子序列所有元素复制完就立刻停止
while(i < nl & j < nr) {
if(left[i] <= right[j]) {
a[k++] = left[i++];
} else {
a[k++] = right[j++];
}
}
//复制剩余的元素
for(; i < nl; i++){
a[k++] = left[i];
}
for(; j < nr; j++) {
a[k++] = right[j];
}
}
//递归划分数组
public void mergeSort(int[] a, int from, int end) {
//单个元素视为已排好序的
if(from < end) {
//从中间划分数组
int mid = (end + from) / 2;
//递归划分数组
mergeSort(a, from, mid);
mergeSort(a, mid+1, end);
merge2(a, from, mid, end);
}
}
//对整个数组排序
public void mergeSort(int[] a) {
mergeSort(a, 0, a.length-1);
}
//打印数组
public void printArr(String str, int[] a) {
System.out.print(str + "\t");
for(int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
//测试数据
public static void main(String[] args) {
MergeSort ms = new MergeSort();
int[] a = {1,4,3,7,5,8,0};
ms.printArr("原始数组为:", a);
ms.mergeSort(a);
ms.printArr("合并排序后:", a);
}
}
分享到:
相关推荐
自动生成500个随机数,然后对这500个随机数进行归并排序
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
根据给定的文件信息,我们将深入探讨两种经典的排序算法——快速排序和归并排序,并结合Java语言实现进行详细解析。 ### 快速排序算法 快速排序是一种高效的排序算法,采用分而治之的策略,其核心思想是选择一个...
java代码-使用java解决java排序之-归并排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
归并排序算法-java 实现 在计算机科学中,排序算法是指将一组无序的数据按照某种规则排列成有序的数据。归并排序(Merge Sort)是一种常用的排序算法,属于分治算法的范畴。下面将详细介绍归并排序算法的java实现。...
在实际应用中,我们通常会使用更高效的排序算法,如快速排序、归并排序或堆排序等,它们在大多数情况下都能提供更好的性能。不过,了解基础的排序算法如选择排序和冒泡排序,对于学习和理解更复杂的算法至关重要。 ...
这篇实验报告将深入探讨两种经典的排序算法——快速排序和归并排序,通过对它们在Java环境中的实现和性能测试,揭示它们在处理不同规模数据时的效率差异。 **快速排序(Quick Sort)** 快速排序由C.A.R. Hoare在...
- 在实际编程中,更高效的排序算法如快速排序、归并排序等更为常用。 在`AlgorithmBubleSort.java`中,我们还可以探讨代码的可读性、空间复杂度以及可能的优化措施,例如使用双指针法减少不必要的比较。这些都将是...
**选择排序**是一种简单直观的排序算法,它的工作原理如下:...在实际应用中,更高效的排序算法如快速排序、归并排序或堆排序等通常会优先考虑。然而,对于教学和理解排序算法的基本原理,选择排序是一个很好的起点。
(10)数据结构之红黑树(三)——删除操作 (11)排序算法(一)——冒泡排序及改进 (12)排序算法(二)——选择排序及改进 (13)排序算法(三)——插入排序及改进 (14)排序算法(四)——归并排序与递归...
在本篇《Java数据结构和算法》学习笔记中,我们将深入探讨递归和归并排序。递归是一种强大的编程技术,常用于解决复杂问题,而归并排序则是利用递归实现的一种高效排序算法。 首先,让我们理解什么是递归。递归是...
在Java面试中,排序算法是常见的话题,因为它在实际编程中有着广泛的应用。这里我们将讨论两种常见的排序算法:归并排序和堆排序。 首先,让我们深入理解归并排序(Merge Sort)。归并排序是一种分治策略,其基本...
### Java版本排序算法详解 #### 插入排序 插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在Java中,我们可以创建一个`...
常见的排序算法有八种,即选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、.radix 排序和基数排序。 一、分类 内部排序和外部排序是两种基本的排序分类。内部排序是指待排序记录存放在计算机随机...
本项目聚焦于一种基础且经典的排序算法——冒泡排序(Bubble Sort),并以Java编程语言作为实现工具。Java是一种广泛使用的面向对象的编程语言,其简洁的语法和丰富的库函数使得实现各种算法变得方便。 冒泡排序是...
这些算法虽然在复杂度上不如高级排序算法如快速排序或归并排序,但它们提供了基础的排序逻辑,有助于理解更复杂的算法思想。 首先,我们来详细讲解插入排序(Insertion Sort)。插入排序的工作原理类似于我们手动...
1. 排序算法:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,理解每种排序算法的工作原理和时间复杂度是至关重要的。 2. 搜索算法:线性搜索、二分搜索、深度优先搜索(DFS)、广度优先搜索...
学习和掌握这些经典的Java排序算法,不仅能提升你的编程技能,还能帮助你在面对不同场景和数据规模时,选择最合适的排序方法,从而提高程序的运行效率。无论是理论学习还是实际开发,这些知识都将是你宝贵的财富。
标题 "各种排序算法java实现" 涉及到的是计算机科学中的一个重要领域——算法,特别是排序算法在Java编程语言中的具体应用。排序算法是数据结构与算法分析中的基础部分,它们用于将一组数据按照特定顺序排列。在这个...