如果没有任何软件包的帮助，您将如何编写这些内容?(与merge(int[] A, int[] l, int[] r)的布局相同)(接受一个数组的输入)。主要问题是转换数组。copyOfRange的非包版本的java到这个代码。谢谢你回答这个问题。
我的另一个问题是如何在参数中实现3个数组的合并函数。
这是我试过的代码:
public static int[] mergeArrays3(int[] a, int[] b, int[] c) {
int[] result = new int[a.length + b.length +c.length];
int i = 0, j = 0, k = 0, l=0;
while(i<a.length &&j<b.length && l<c.length)
{
// if (b[i] < a[j] || b[i] <c[i]) {
// result[k] = c[i];
// j++;
// }
if (c[i] < b[j] || c[i] <a[i]) {
result[k] = c[i];
l++;
}
if (a[i] < b[j] || a[i] <c[i]) {
result[k] = a[i];
i++;
}
else {
result[k] = b[j];
j++;
}
k++;
}
while(i<a.length)
{
result[k] = a[i];
i++;
k++;
}
while(j<b.length)
{
result[k] = b[j];
j++;
k++;
}
while(l<c.length)
{
result[k]=c[l];
l++;
k++;
}
return result;
}
```
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException{
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j++) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length/2;
//changed range of leftArray from 0-to-q to 0-to-(q-1),how would you edit Arrays.copyOfRange to manually make the same function without using any packages?
*int[] leftArray = Arrays.copyOfRange(A, 0, q-1);
//changed range of rightArray from q-to-A.length to q-to-(A.length-1)
int[] rightArray = Arrays.copyOfRange(A,q,A.length-1);*
mergeSort(leftArray);
mergeSort(rightArray);
merge(A,leftArray,rightArray);
}
}
static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
//int[] a = new int[totElem];
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
}
else {
a[i] = r[ri];
i++;
ri++;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
//return a;
}
}
这个方法没有Arrays.copyOfRange那么快，并且它不能涵盖所有情况，例如负索引，还需要检查大小
private static int[] copyArray(int[] original, int from, int to) {
int [] res = new int[to-from];
for (int i = from; i< to; i++) {
res[i - from] = original[i];
}
return res;
}
使用for循环对一次性数组拷贝进行自顶向下的归并排序，并在每一级递归时交替参数以改变归并方向。MergeSort是分配并复制到第二个数组的入口函数。MergeSortR是递归函数。除非所有3个子数组至少有一个元素，否则永远不会调用Merge。Merge中的嵌套if | else只需要2个比较来确定最小的元素，但是使用重复的代码来处理a[a2]是最小元素的情况。(在C/c++中，goto可以用来避免重复的代码)。bb为开始索引，ee为结束索引。
static void MergeSort(int[] a)
{
if(a.length < 2) // if < 2 elements, nothing to sort
return;
int [] b = new int[a.length]; // b[] = a[] | int[]b = a.clone();
for(int i = 0; i < a.length; i++)
b[i] = a[i];
MergeSortR(b, a, 0, a.length); // sort b[] to a[]
}
static void MergeSortR(int[] b, int[] a, int bb, int ee)
{
if(ee - bb < 2) // if < 2 elements, nothing to sort
return;
if(ee - bb == 2){ // if 2 elements
if(a[bb] > a[bb+1]){
int t = a[bb];
a[bb] = a[bb+1];
a[bb+1] = t;
}
return;
}
int m1 = bb+(ee+0-bb)/3; // split into 3 parts
int m2 = m1+(ee+1-bb)/3;
MergeSortR(a, b, bb, m1); // sort a[] to b[]
MergeSortR(a, b, m1, m2);
MergeSortR(a, b, m2, ee);
Merge(b, a, bb, m1, m2, ee); // merge b[] to a[]
}
static void Merge(int[] a, int[] b, int bb, int m1, int m2, int ee)
{
int b0 = bb; // b[] index
int a0 = bb; // a[] indexes
int a1 = m1;
int a2 = m2;
while(true){ // 3 way merge
if(a[a0] <= a[a1]){
if(a[a0] <= a[a2]){
b[b0] = a[a0]; // a[a0] smallest
b0++;
a0++;
if(a0 < m1) // if not end of run
continue; // continue
a0 = a1; // else setup for 2 way merge
a1 = a2;
m1 = m2;
m2 = ee;
break;
} else {
b[b0] = a[a2]; // a[a2] smallest
b0++;
a2++;
if(a2 < ee) // if not end of run
continue; // continue
break; // else setup for 2 way merge
}
} else {
if(a[a1] <= a[a2]){
b[b0] = a[a1]; // a[a1] smallest
b0++;
a1++;
if(a1 < m2) // if not end of run
continue; // continue
a1 = a2; // else setup for 2 way merge
m2 = ee;
break;
} else {
b[b0] = a[a2]; // a[a2] smallest
b0++;
a2++;
if(a2 < ee) // if not end of run
continue; // continue
break; // else setup for 2 way merge
}
}
}
while(true){ // 2 way merge
if(a[a0] <= a[a1]){
b[b0] = a[a0];
b0++;
a0++;
if(a0 < m1) // if not end of run
continue; // continue
a0 = a1; // else setup for copy
m1 = m2;
break;
}else{
b[b0] = a[a1];
b0++;
a1++;
if(a1 < m2) // if not end of run
continue; // continue
break; // else setup for copy
}
}
while(true){ // copy rest of remaining run
b[b0] = a[a0];
b0++;
a0++;
if(a0 < m1)
continue;
break;
}
}