java 组合和排序两个数组Java？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11164383/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
combining and sorting two arrays Java?
提问by user1229164
So basically there are two separate presorted arrays, and you have to combine them and sort them (without sort() methods of course). Here is my code:
所以基本上有两个单独的预排序数组，您必须将它们组合起来并对它们进行排序（当然没有 sort() 方法）。这是我的代码：
public static void main(String[] args) {
int a [] = {3,5,7,9,12,14, 15};
int b [] = {6 ,7, 10};
int j = 0;
//output array should be 3,5,6,7,7,9,10,12,14,15
int c [] = new int[a.length+b.length];//10 values
for (int i = 0;i<b.length;i++){
while(b[i]>a[j]){
c[j] = a[j] ;
j++;
}
if(b[i] == a[j]){
c[j] = b[i];
c[j+1] = a[j];
}
c[j] = b[i];
j++;
}
for(int i = 0;i<c.length;i++)
System.out.println(c[i]);
}
I'm guessing the zeros I am getting are from a mistake in one of the booleans (< & >), but I cant seem to figure it out. It works fine for the first 4, but once I get to the repeating 7's, it just goes crazy.
我猜我得到的零是因为其中一个布尔值 (< & >) 的错误，但我似乎无法弄清楚。它适用于前 4 个，但一旦我到达重复的 7 个，它就会变得疯狂。
Please help me understand, don't just change the code.
请帮助我理解，不要只是更改代码。
回答by hattenn
This is how it should be in a simple way:
这应该是一种简单的方式：
public static void main(String[] args) {
int a [] = {3,5,7,9,12,14, 15};
int b [] = {6 ,7, 10};
int j = 0, k = 0;
//output array should be 3,5,6,7,7,9,10,12,14,15
int c [] = new int[a.length+b.length];//10 values
// we're filling c with the next appropriate number
// we start with checking a[0] and b[0] till we add
// all the elements
for (int i = 0; i < c.length; i++) {
// if both "a" and "b" have elements left to check
if (j < a.length && k < b.length) {
// check if "b" has a smaller element
if (b[k] < a[j]) {
// if so add it to "c"
c[i] = b[k];
k++;
}
// if "a" has a smaller element
else {
// add it to "c"
c[i] = a[j];
j++;
}
}
// if there are no more elements to check in "a"
// but there are still elements to check in "b"
else if (k < b.length) {
// add those elements in "b" to "c"
c[i] = b[k];
k++;
}
// if there are no more elements to check in "b"
// but there are still elements to check in "a"
else {
// add those elements in "a" to "c"
c[i] = a[j];
j++;
}
}
for(int i = 0; i < c.length; i++)
System.out.println(c[i]);
}
Hope it helps.
希望能帮助到你。
回答by Akhi
You can try this code.
你可以试试这个代码。
public static void main(String[] args) {
int a[] = { 3, 5, 7, 9, 12, 14, 15 };
int b[] = { 6, 7, 10 };
// output array should be 3,5,6,7,7,9,10,12,14,15
int alen = a.length;
int blen = b.length;
int c[] = new int[a.length + b.length];// 10 values
int s[] = null;
int[] l = null;
if (alen < blen) {
s = a;
l = b;
} else {
s = b;
l = a;
}
// Constructing Combined Array
for (int i = 0, p = 0; i < c.length; i++, p++) {
if (i == s.length) {
p = 0;
}
if (i < s.length) {
c[i] = s[p];
} else {
c[i] = l[p];
}
}
//Sorting the C array
for (int i = 1; i < c.length; i++) {
int j = i;
int B = c[i];
while ((j > 0) && (c[j - 1] > B)) {
c[j] = c[j - 1];
j--;
}
c[j] = B;
}
for (int i = 0; i < c.length; i++)
System.out.print(c[i]);
}
回答by jakkula vinay
public class Combinearray {
public static void main(String[] args) {
int[] array1= {5,4,6,2,1};
int[] array2= {2,5,8,4,1,6,4};
int m=array1.length;
int n=array2.length;
int[] array3=new int[m+n];
int a=1;
for(int i=0;i<m;i++) {
array3[i]=array1[i];//array1 is copied to array3
}
for(int i=0;i<n;i++) {
array3[m-1+a]=array2[i];//array2 is copied to array3
a++;
}
//array3 is combined array
int l=array3.length;
int temp[]=new int[l];
for(int i=0;i<l;i++) {
for(int j=i+1;j<l;j++) {
if(array3[i]>array3[j]) {
temp[i]=array3[i];
array3[i]=array3[j];
array3[j]=temp[i];
}
}
}
System.out.println("sorted array is ");
System.out.print("[");
for(int i=0;i<l;i++) {
System.out.print(array3[i]+" ");
}
System.out.print("]");
}
}
回答by ArtemStorozhuk
Actually it's better to say merging(not combining) two arrays.
实际上最好说合并（而不是组合）两个数组。
Simple algorithm (taken from this article) for merging sorted arrays Aand B[0..n-1]into result C[0..m+n-1]:
用于将排序的数组A和B[0..n-1]合并到结果C[0..m+n-1] 的简单算法（取自本文）：
- Introduce read-indices i, jto traverse arrays A[0..m-1]and B, accordingly. Introduce write-index kto store position of the first free cell in the resulting array. By default i= j= k= 0.
- At each step: if both indices are in range (i< mand j< n), choose minimum of (A[i], B[j]) and write it to C[k]. Otherwise go to step 4.
- Increase kand index of the array, algorithm located minimal value at, by one. Repeat step 2.
- Copy the rest values from the array, which index is still in range, to the resulting array.
- 相应地引入读取索引i, j以遍历数组A[0..m-1]和B。引入 write-index k来存储结果数组中第一个空闲单元的位置。默认情况下i= j= k= 0。
- 在每一步：如果两个索引都在范围内（i< m和j< n），则选择（A[i], B[j]）中的最小值并将其写入C[k]。否则转到第 4 步。
- 将数组的k和索引值加 1，算法位于最小值处。重复步骤 2。
- 将索引仍在范围内的数组中的其余值复制到结果数组中。
Hope it helps.
希望能帮助到你。
回答by K_Anas
Try this, your error is you are using the same cellular index for array A and array C:
试试这个，你的错误是你对数组 A 和数组 C 使用相同的细胞索引：
public class MainClass {
public static void main(String[] args) {
int[] arrayA = { 23, 47, 81, 95 };
int[] arrayB = { 7, 14, 39, 55, 62, 74 };
int[] arrayC = new int[10];
merge(arrayA, arrayA.length, arrayB, arrayB.length, arrayC);
for (int i : arrayC) {
System.out.println(i);
}
}
public static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB, int[] arrayC) {
int arrayAIndex = 0, arrayBIndex = 0, arrayCIndex = 0;
while (arrayAIndex < sizeA && arrayBIndex < sizeB)
if (arrayA[arrayAIndex] < arrayB[arrayBIndex])
arrayC[arrayCIndex++] = arrayA[arrayAIndex++];
else
arrayC[arrayCIndex++] = arrayB[arrayBIndex++];
while (arrayAIndex < sizeA)
arrayC[arrayCIndex++] = arrayA[arrayAIndex++];
while (arrayBIndex < sizeB)
arrayC[arrayCIndex++] = arrayB[arrayBIndex++];
}
}
This is another version
这是另一个版本
// size of C array must be equal or greater than
// sum of A and B arrays' sizes
public void merge(int[] A, int[] B, int[] C) {
int i, j, k, m, n;
i = 0;
j = 0;
k = 0;
m = A.length;
n = B.length;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
if (i < m) {
for (int p = i; p < m; p++) {
C[k] = A[p];
k++;
}
} else {
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
回答by Stefan Haustein
Use aiand bifor the indices in both source arrays and cias the index for the destination array.
将ai和bi用于源数组ci中的索引和目标数组的索引。
You only need one loop.
你只需要一个循环。
Try to keep this very clear and advance in cby exactly one element at each iteration.
尽量保持这一点非常清楚，并c在每次迭代中准确推进一个元素。
In the loop, check wether the end of one array was reached. If so, just take an element from the other array. Otherwise, take only the smaller element of a[ai]and b[bi]and increment the corresponding index.
在循环中，检查是否到达了一个数组的末尾。如果是这样，只需从另一个数组中取出一个元素。否则，只取a[ai]and 中较小的元素b[bi]并增加相应的索引。
It is very easy to make mistakes in mergesort (or in any code where two arrays need to be walked in parallel) by thinking "hey I can go along with a while loop instead of just doing a single if", but then you typically have two loops nested in a third one, and for each of the loops you have to do the right bounds checks, and there is typically no significant gain in performance.
很容易在归并排序（或任何需要并行处理两个数组的代码）中犯错误，因为认为“嘿，我可以用一个 while 循环而不是只执行一个 if”，但是你通常有两个循环嵌套在第三个循环中，对于每个循环，您必须进行正确的边界检查，通常不会显着提高性能。
p.s. Doing one main loop and then two cleanup loops after the main loop is fine, just avoid nested loops if they are not necessary, in particular in interviews where this may also cause confusion when calculating the runtime.
ps 做一个主循环，然后在主循环之后做两个清理循环就可以了，如果没有必要，只需避免嵌套循环，特别是在面试中，这也可能在计算运行时时造成混乱。
