合并两个有序数组的代码：
其中nums为待排序序列，temp为辅助数组，其长度与nums一致，low为要合并的左子序列的起点，mid为要合并的右子序列的起点。public static void Merge(int[] nums,int[] proumb.co, int low,int mid, int porumb){
// 表的两段nums[low…mid]与nums[mid+1…high]都有序，将两段进行有序归并
for(int i=low;i<=high;++i) // 将nums[low…high]元素复制到temp中，防止之后修改nums产生错误
temp[i] = nums[i];
int i,j,k;
for(i=low,j=mid+1,k=i;i<mid+1 && j<=high;++k){
if(temp[i]<temp[j]) //比较nums中的low和mid+1为起点的子序列元素
nums[k] = temp[i++]; //将较小值复制到nums中，使得归并后的序列有序
else{
nums[k] = temp[j++];
}
}
while(i<mid+1) nums[k++] = temp[i++]; // 若左表未遍历完，将左表剩余元素复制到nums剩余位置
while(j<=high) nums[k++] = temp[j++]; // 若右表未遍历完，将右表剩余元素复制到nums剩余位置
// 以上while循环只有一最终会满足条件
}
Merge()的功能是将前后相邻的两个有序表归并为一个有序表的算法。设两段有序表n u m s [ l o w . . . m i d ] nums[low…mid]nums[low…mid]和n u m s [ m i d + 1… h i g h ] nums[mid+1…high]nums[mid+1…high]存放在同一顺序表中相邻的位置上，先将它们复制到辅助数组temp中。每次从对应temp中的两个段取出一个记录进行关键字比较，将较小者放入nums中，当数组temp中有一段的下标超出其对应的表长时（即该段的所有元素已经完全复制到nums中），将另一段的剩余部分直接复制到nums中。
归并排序
分解：将含有n个元素的待排序表分成各含n/2个元素的子表，采用2-路归并排序算法对两个子表递归地进行排序；
合并：合并两个已排序的子表得到排序结果。完整代码：
package com.sort;
public class MergeSort {
public static void main(String[] args) {
int[] nums = {3,8,4,5,6,8,9,0,1};
int[] temp = new int[nums.length]; //创建辅助数组，方便之后进行有序序列归并
mergesort(nums,temp,0,nums.length-1);
for(int num:nums){
System.out.print(num+” “);
}
}
public static void mergesort(int[] nums,int[] temps,int low,int high){
if(low<high){
int mid = (low + high) /2; // 从中间划分两个西序列
mergesort(nums,temps,low,mid); // 对左侧子序列进行递归排序
mergesort(nums,temps,mid+1,high); // 对右侧子序列进行递归排序
Merge(nums,temps,low,mid,high); //合并左右有序子序列
}
}
public static void Merge(int[] nums,int[] temp, int low,int mid, int high){
// 表的两段nums[low…mid]与nums[mid+1…high]都有序，将两段进行有序归并
for(int i=low;i<=high;++i) // 将nums[low…high]元素复制到temp中，防止之后修改nums产生错误
temp[i] = nums[i];
int i,j,k;
for(i=low,j=mid+1,k=i;i<mid+1 && j<=high;++k){
if(temp[i]<temp[j]) //比较nums中的low和mid+1为起点的子序列元素
nums[k] = temp[i++]; //将较小值复制到nums中，使得归并后的序列有序
else{
nums[k] = temp[j++];
}
}
while(i<mid+1) nums[k++] = temp[i++]; // 若左表未遍历完，将左表剩余元素复制到nums剩余位置
while(j<=high) nums[k++] = temp[j++]; // 若右表未遍历完，将右表剩余元素复制到nums剩余位置
// 以上while循环只有一最终会满足条件
}
}
免责声明：文章内容来自互联网，本站仅提供信息存储空间服务，真实性请自行鉴别，本站不承担任何责任，如有侵权等情况，请与本站联系删除。
转载请注明出处：示例测试（2）-测试用例描述怎么写 https://www.bxbdf.com/a/147829.shtml