`

两个数组的归并

 
阅读更多
package org.son;

import java.lang.String;
import java.lang.System;
import java.util.Arrays;

public class Demo {
	public static void main(String[] args) {
		int[] a = { -1, 5, 9, 15, 85, 98, 100 };
		int[] b = { -2, 6, 8, 14, 73, 85, 97 };
		System.out.println(checkSort(a));
		sort(a);
		System.out.println(checkSort(a));
		System.out.println(Arrays.toString(merge(a, b)));

	}

	public static boolean checkSort(int[] a) {
		// 使用插入排序进行验证
		for (int x = 0; x < a.length - 1; x++) {
			for (int y = x; y > 0; y--) {
				if (a[y - 1] > a[y])
					return false;
			}
		}
		return true;
	}

	public static void sort(int[] a) {
		// 使用了插入排序
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = i; j > 0 && a[j - 1] > a[j]; j--) {
				int temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}
	}

	private static int[] merge(int[] a, int[] b) {
		int[] result = new int[a.length + b.length];
		if (checkSort(a) && checkSort(b)) {
			// 两个数组都处于排序状态
			int i = 0, j = 0, k = 0;
			while (i <= a.length - 1 && j <= b.length - 1) {
				// 两个数组都没有数据用完
				if (a[i] <= b[j])
					result[k++] = a[i++];
				if (b[j] < a[i])
					result[k++] = b[j++];
			}
			// a数组未用完,b数组用完了
			while (i <= a.length - 1 && j > b.length - 1) {
				result[k++] = a[i++];
			}
			// b数组未用完,a数组用完了
			while (j <= b.length - 1 && i > a.length - 1) {
				result[k++] = b[j++];
			}
		} else {
			// 如果数组a属于非排序状态则对a进行排序
			if (!checkSort(a))
				sort(a);
			// 如果数组b属于非排序状态则对b进行排序
			if (!checkSort(a))
				sort(b);
			merge(a, b);
		}
		return result;
	}
}

 

分享到:
评论

相关推荐

    编写一个程序,将两个元素从小到大有序的一维数组归并成一个有序的一维数组。

    【输出形式】程序将两个有序一维数组合并为一个有序数组并按照从小到大顺序输出。每个元素输出时用空格分隔,最后一个输出之后没有空格。 【样例输入】 6 2 5 8 11 20 35 4 1 6 15 60 【样例输出】1 2 5 6 8 11 15 ...

    两个有序数组归并排序

    给定两个有序数组a b 使合并后的数组仍然有序 归并算法的事件复杂度为O logn

    将两个有序数组,合并成另一个有序的数组,升序

    实现这一算法的主要思路是利用while循环来逐步比较两个数组当前索引位置的元素,并将较小的元素放入数组c中。具体来说,如果数组a当前的元素小于数组b当前的元素,那么将a的元素赋值给c,并将ai的值加一,同时ci的值...

    树状数组归并排序应用计算数组的小和1

    树状数组归并排序应用计算数组的小和 树状数组是一种高效的数据结构,用于计算数组的小和。小和是指数组中每个元素左侧比它小的元素之和。树状数组可以在O(n)的时间复杂度内计算小和。 在本文中,我们将使用python...

    C语言用分治法实现数组归并排序算法实现

    (3)回溯时合并子问题的解,在两个子问题的解中大者取大,小者取小,即合并为当前问题的解。 归并排序的过程是,将数组分为许多的组,即将数组元素多的数组分为数组元素少的数组,然后再将其合并。它的优点是,...

    随机数组的归并问题JAVA代码

    题目描述: 随机数组的归并问题需求:生成两个任意的随机数组,并将这两个数组按照数字大小按顺序归并到一个新数组中

    归并排序(链表和数组) 数组和链表.pdf

    在数组归并排序中,我们需要定义一个数组,然后将数组分解成多个子数组。接着,我们可以使用递归的方法来实现数组归并排序。首先,我们需要找到数组的中间索引,然后将数组分解成两个子数组,接着对每个子数组进行...

    归并排序算法实现

    利用的是递归的思想 核心是将已经排好序的两个数组归并成一个有序数组。 输入:数组的长度 输出:排好序的输入 参考:算法导论英文第二版P29

    4-14_lv一维数组中所有元素之和_

    4. 数组操作节点:LV库中包含多种用于数组操作的节点,如“Add”(加法)节点,可以将两个数组相加;“Sum”(求和)节点,用于计算数组所有元素的总和。 四、具体到"4-14.vi"程序 在这个VI中,很可能是通过以下...

    合并两有序数组

    将一个数组中,已经有序的两部分,重新进行排序,得到排序后的有序完整数组。

    C语言演示对归并排序算法的优化实现

    如果有两个数组已经有序,那么可以把这两个数组归并为更大的一个有序数组。归并排序便是建立在这一基础上。要将一个数组排序,可以将它划分为两个子数组分别排序,然后将结果归并,使得整体有序。子数组的排序同样...

    Merge(合并两个已排好序的数组)

    基本思路是设置两个指针分别指向两个数组的起始位置,比较两个指针所指元素的大小,将较小的元素添加到新数组,并将对应的指针向后移动一位。这个过程持续到其中一个数组的所有元素都被添加到新数组为止,然后将另一...

    五个排序算法(快速,希尔,插入,归并排序)

    归并排序将数组分为两半,分别对左右两半进行排序,然后将两个有序的部分合并成一个大的有序序列。这个过程可以递归进行,直到所有元素都在一个单元内。归并排序的时间复杂度是O(n log n),但需要额外的存储空间,...

    c语言编程题之数组操作合并两个有序数组.zip

    这个方法的核心思想是从两个数组的起始位置开始,比较两个数组的当前元素,将较小的元素放入结果数组,并移动较小元素所在数组的指针。重复此过程直到一个数组遍历完,然后将另一个数组剩余的元素依次添加到结果数组...

    合并两个已经排序的数组为另一个数组算法

    合并两个已排序数组的基本思想是利用两个指针分别指向两个数组的起始位置,然后比较两个指针所指向的元素大小,较小的元素先被放入结果数组中,并将其对应的指针后移一位。重复此过程直至所有元素都被放入结果数组。...

    C语言归并算法

    该函数首先将两个数组的元素分别存储在两个数组L和R中,然后比较两个数组的元素,选择较小的元素放入num数组中,以保持数组的有序性。 在merge函数中,我们使用了动态内存分配来声明两个数组L和R,以便存储两个有序...

    java-leetcode题解之第88题合并两个有序数组.zip

    6. **效率分析**:由于两个数组都是有序的,所以这个方法的时间复杂度是O(m+n),其中m和n分别是两个数组的长度。空间复杂度是O(1),因为我们只使用了常数级别的额外空间。 7. **LeetCode平台**:熟悉LeetCode的提交...

    C++实现两个有序数组的合并

    双指针算法是指使用两个指针,分别指向两个数组的尾部,然后从后往前复制每个数字,从而减少移动的次数,提高效率。 以下是C++实现数组合并的示例代码: ```cpp int * insert(int *str1, int *str2, int n1, int n2...

    归并排序C语言实现

    3. **合并操作**:在归并排序中,合并是将两个已经排序的子数组合并成一个有序数组的过程。这个过程中需要用到额外的存储空间,通常是一个与原数组同样大小的临时数组。比较两个子数组的元素,依次将较小的元素放入...

    数据结构实验报告1-线性表-两个有序表的归并-实验内容及要求.docx

    3. **归并两个有序线性表**:接下来,需要实现两个有序线性表的归并操作,即将两个有序线性表合并成一个新的有序线性表。 4. **输出归并后的有序线性表**:最后,程序需要输出归并后的有序线性表。 #### 存储结构的...

Global site tag (gtag.js) - Google Analytics