归并排序：把一个数组分成两半，排序每一半，然后把两半归并成一个有序数组。每一半再细分成两半，形成一个递归。
MergeSort.java 代码
- public class MergeSort {
-
- private static int[] arrayMergeSort = { 43, 36, 11, 10, 29, 58, 15, 9 };
-
- public static void main(String[] args) {
- mergeSort();
- System.out.print("after merge sort: ");
- disp("", arrayMergeSort);
- }
-
- private static void mergeSort() {
- int[] workArray = new int[arrayMergeSort.length];
- recMergeSort(workArray, 0, arrayMergeSort.length - 1);
- }
-
- private static void recMergeSort(int[] workArray, int lowerBound,
- int upperBound) {
- if (lowerBound == upperBound) {
- return;
- } else {
- int mid = (lowerBound + upperBound) / 2;
- recMergeSort(workArray, lowerBound, mid);
- recMergeSort(workArray, mid + 1, upperBound);
- merge(workArray, lowerBound, mid + 1, upperBound);
- }
- }
-
- private static void merge(int[] workArray, int lowerPos, int upperPos,
- int upperBound) {
- int i = 0;
- int lowerBound = lowerPos;
- int mid = upperPos - 1;
- int num = upperBound - lowerBound + 1;
-
- while (lowerPos <= mid && upperPos <= upperBound) {
- if (arrayMergeSort[lowerPos] < arrayMergeSort[upperPos])
- workArray[i++] = arrayMergeSort[lowerPos++];
- else
- workArray[i++] = arrayMergeSort[upperPos++];
- }
-
- while (lowerPos <= mid) {
- workArray[i++] = arrayMergeSort[lowerPos++];
- }
- while (upperPos <= upperBound) {
- workArray[i++] = arrayMergeSort[upperPos++];
- }
-
- for (i = 0; i < num; i++) {
- arrayMergeSort[lowerBound + i] = workArray[i];
- }
- disp("temp array: ", workArray);
- disp("sort array: ", arrayMergeSort);
- }
-
- private static void disp(String s, int[] array) {
- System.out.print(s);
- for (int i = 0; i < array.length; i++) {
- System.out.print(array[i] + " ");
- }
- System.out.println("");
- }
-
- }
实际运行结果如下：
- temp array: 36 43 0 0 0 0 0
- sort array: 36 43 11 10 29 58 15
- temp array: 10 11 0 0 0 0 0
- sort array: 36 43 10 11 29 58 15
- temp array: 10 11 36 43 0 0 0
- sort array: 10 11 36 43 29 58 15
- temp array: 29 58 36 43 0 0 0
- sort array: 10 11 36 43 29 58 15
- temp array: 15 29 58 43 0 0 0
- sort array: 10 11 36 43 15 29 58
- temp array: 10 11 15 29 36 43 58
- sort array: 10 11 15 29 36 43 58
- after merge sort: 10 11 15 29 36 43 58
分享到：
相关推荐
《数据结构》严蔚敏版是计算机科学的经典教材，其中对归并排序有深入的阐述。下面我们将详细探讨归并排序的原理、实现方式以及其在实际应用中的优势。 一、归并排序的基本概念 归并排序的核心思想是将大问题分解为...
在内部排序（数据全部在内存中）中，归并排序在处理大型数据集时表现出色。而在外部排序（数据无法全部加载到内存）中，由于磁盘读写操作的代价，归并排序通过减少磁盘I/O次数来提高效率。 7. **优化技巧**： - **...
关于序列的归并排序，涉及到序列的长度
数据结构之归并排序的实例详解主要介绍了数据结构之归并排序的实例详解的相关资料，以下是对归并排序的详细介绍。 基本思想 归并排序是建立在二路归并和分治法的基础上的一个高效排序算法，将已有序的子序列合并，...
数据结构是计算机科学中的核心概念，它涉及到如何高效地存储和组织数据，以便进行各种操作。其中，排序算法是数据结构领域的一个重要分支，它的目标是将无序的数据序列整理成有序序列。归并排序（Merge Sort）是一种...
首先，堆排序是一种基于比较的排序算法，利用了二叉堆的数据结构。二叉堆是一个完全二叉树，可以分为最大堆或最小堆，其中每个父节点的值都大于或等于其子节点。堆排序的过程包括构建初始堆和调整堆。首先，将无序...
本主题将深入探讨四种常见的排序算法：归并排序、快速排序以及与链表相关的排序方法。 首先，我们来讨论归并排序（Merge Sort）。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题，然后逐步合并这些...
### 数据结构 VC实现 归并排序 #### 一、归并排序原理介绍 归并排序是一种采用分治法策略的高效排序算法。其核心思想是将待排序的序列分为尽可能相等的两部分，分别对这两部分进行排序，然后将排好序的两部分合并...
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
**归并排序是一种高效...通过理解归并排序的工作原理和C语言实现的细节，你可以更好地掌握数据结构中的排序算法，并在实际编程中灵活应用。无论是在学习阶段还是在实际开发中，掌握这种高效的排序方法都是非常有益的。
- **时间复杂度**：归并排序的时间复杂度为O(n log n)，无论输入数据的初始顺序如何，这个复杂度始终保持不变，因此对于大数据集非常高效。 - **空间复杂度**：由于需要额外的空间来存储子数组，在合并过程中，归并...
数据结构-归并排序 PPT文档
数据结构中的内部排序法 归并排序 非常的好用
### 归并排序：经典数据结构算法 #### 算法概述 归并排序是一种经典的、高效的基于比较的排序算法，其基本思想是采用分治法（Divide and Conquer）。该算法首先将待排序的序列分成若干个子序列，每个子序列都是...
不同之处在于，归并排序不使用二分查找，而是将数组分为两半，然后对每一半进行排序，再合并。归并排序在MATLAB中实现时，也需要递归地将数组划分为更小的部分，直到每个部分仅包含一个元素，然后逐步合并这些元素，...
在数据结构-归并排序的实验中，重点是理解和实现二路归并排序算法，以及递归地处理数组的拆分和归并过程。** ### 1. 算法原理 归并排序的基本思想是将待排序的数据分成两个子序列，每个子序列都是有序的，然后将这...
多路归并排序在处理大规模数据集时特别有用，尤其是在外部排序场景下，即数据量太大无法完全加载到内存中时。在这种情况下，多路归并排序可以通过多次读写磁盘来完成排序任务，相比其他算法如快速排序，它可以更有效...
C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增排序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中...
**三路归并排序**是一种高效的排序算法，尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想，但将其分为三...在C语言中，通过合理的指针管理和递归结构，可以实现清晰且高效的三路归并排序算法。
实现以下常用的内部排序算法并进行性能比较："直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...