按排序顺序合并两个未排序的数组
原文： https://www.geeksforgeeks.org/merging-two-unsorted-arrays-sorted-order/
编写一个SortedMerge()函数，该函数接受两个列表，每个列表都未排序，然后将两个列表合并为一个新列表，该列表以排序（递增）的顺序排列。 SortedMerge()应该返回新列表。
示例：
Input : a[] = {10, 5, 15}
b[] = {20, 3, 2}
Output : Merge List :
{2, 3, 5, 10, 15, 20}
Input : a[] = {1, 10, 5, 15}
b[] = {20, 0, 2}
Output : Merge List :
{0, 1, 2, 5, 10, 15, 20}
有很多情况需要处理：a或b可能为空，在处理过程中a或b可能先用尽，最后在遍历a和b时，存在从零启动结果列表并构建它的问题。
方法 1（先连接，然后排序）：
在这种情况下，我们首先附加两个未排序的列表。 然后，我们仅对连接后的列表进行排序。
C++
// CPP program to merge two unsorted lists
// in sorted order
#include <bits/stdc++.h>
using namespace std;
// Function to merge array in sorted order
void sortedMerge(int a[], int b[], int res[],
int n, int m)
{
// Concatenate two arrays
int i = 0, j = 0, k = 0;
while (i < n) {
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) {
res[k] = b[j];
j += 1;
k += 1;
}
// sorting the res array
sort(res, res + n + m);
}
// Driver code
int main()
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
// Final merge list
int res[n + m];
sortedMerge(a, b, res, n, m);
cout << "Sorted merged list :";
for (int i = 0; i < n + m; i++)
cout << " " << res[i];
cout << "n";
return 0;
}
Java
// Java Code for Merging two unsorted
// arrays in sorted order
import java.util.*;
class GFG {
// Function to merge array in sorted order
public static void sortedMerge(int a[], int b[],
int res[], int n,
int m)
{
// Concatenate two arrays
int i = 0, j = 0, k = 0;
while (i < n) {
res[k] = a[i];
i++;
k++;
}
while (j < m) {
res[k] = b[j];
j++;
k++;
}
// sorting the res array
Arrays.sort(res);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = a.length;
int m = b.length;
// Final merge list
int res[]=new int[n + m];
sortedMerge(a, b, res, n, m);
System.out.print("Sorted merged list :");
for (int i = 0; i < n + m; i++)
System.out.print(" " + res[i]);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python
# Python program to merge two unsorted lists
# in sorted order
# Function to merge array in sorted order
def sortedMerge(a, b, res, n, m):
# Concatenate two arrays
i, j, k = 0, 0, 0
while (i < n):
res[k] = a[i]
i += 1
k += 1
while (j < m):
res[k] = b[j]
j += 1
k += 1
# sorting the res array
res.sort()
# Driver code
a = [ 10, 5, 15 ]
b = [ 20, 3, 2, 12 ]
n = len(a)
m = len(b)
# Final merge list
res = [0 for i in range(n + m)]
sortedMerge(a, b, res, n, m)
print "Sorted merged list :"
for i in range(n + m):
print res[i],
# This code is contributed by Sachin Bisht
C#
// C# Code for Merging two
// unsorted arrays in sorted order
using System;
class GFG {
// Function to merge array in sorted order
public static void sortedMerge(int []a, int []b,
int []res, int n,
int m)
{
// Concatenate two arrays
int i = 0, j = 0, k = 0;
while (i < n) {
res[k] = a[i];
i++;
k++;
}
while (j < m) {
res[k] = b[j];
j++;
k++;
}
// sorting the res array
Array.Sort(res);
}
/* Driver program to test above function */
public static void Main()
{
int []a = {10, 5, 15};
int []b = {20, 3, 2, 12};
int n = a.Length;
int m = b.Length;
// Final merge list
int []res=new int[n + m];
sortedMerge(a, b, res, n, m);
Console.Write("Sorted merged list :");
for (int i = 0; i < n + m; i++)
Console.Write(" " + res[i]);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to merge two unsorted lists
// in sorted order
// Function to merge array in sorted order
function sortedMerge($a, $b, $n, $m)
{
// Concatenate two arrays
$res = array();
$i = 0; $j = 0; $k = 0;
while ($i < $n)
{
$res[$k] = $a[$i];
$i += 1;
$k += 1;
}
while ($j < $m)
{
$res[$k] = $b[$j];
$j += 1;
$k += 1;
}
// sorting the res array
sort($res);
echo "Sorted merged list :";
for ($i = 0; $i < count($res); $i++)
echo $res[$i] . " ";
}
// Driver code
$a = array( 10, 5, 15 );
$b = array( 20, 3, 2, 12 );
$n = count($a);
$m = count($b);
// Final merge list
sortedMerge($a, $b, $n, $m);
// This code is contributed by Rajput-Ji.
?>
输出：
Sorted merged list : 2 3 5 10 12 15 20
时间复杂度：O((n + m) (log(n + m)))。
辅助空间：O((n + m))。
方法 2（先排序然后合并）：
我们首先将两个给定的数组分别排序。 然后，我们简单地合并两个排序的数组。
C++
// CPP program to merge two unsorted lists
// in sorted order
#include <bits/stdc++.h>
using namespace std;
// Function to merge array in sorted order
void sortedMerge(int a[], int b[], int res[],
int n, int m)
{
// Sorting a[] and b[]
sort(a, a + n);
sort(b, b + m);
// Merge two sorted arrays into res[]
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) {
res[k] = a[i];
i += 1;
k += 1;
} else {
res[k] = b[j];
j += 1;
k += 1;
}
}
while (i < n) { // Merging remaining
// elements of a[] (if any)
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) { // Merging remaining
// elements of b[] (if any)
res[k] = b[j];
j += 1;
k += 1;
}
}
// Driver code
int main()
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
// Final merge list
int res[n + m];
sortedMerge(a, b, res, n, m);
cout << "Sorted merge list :";
for (int i = 0; i < n + m; i++)
cout << " " << res[i];
cout << "n";
return 0;
}
Java
// JAVA Code for Merging two unsorted
// arrays in sorted order
import java.util.*;
class GFG {
// Function to merge array in sorted order
public static void sortedMerge(int a[], int b[],
int res[], int n,
int m)
{
// Sorting a[] and b[]
Arrays.sort(a);
Arrays.sort(b);
// Merge two sorted arrays into res[]
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) {
res[k] = a[i];
i += 1;
k += 1;
} else {
res[k] = b[j];
j += 1;
k += 1;
}
}
while (i < n) { // Merging remaining
// elements of a[] (if any)
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m) { // Merging remaining
// elements of b[] (if any)
res[k] = b[j];
j += 1;
k += 1;
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
int a[] = { 10, 5, 15 };
int b[] = { 20, 3, 2, 12 };
int n = a.length;
int m = b.length;
// Final merge list
int res[] = new int[n + m];
sortedMerge(a, b, res, n, m);
System.out.print( "Sorted merged list :");
for (int i = 0; i < n + m; i++)
System.out.print(" " + res[i]);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python
# Python program to merge two unsorted lists
# in sorted order
# Function to merge array in sorted order
def sortedMerge(a, b, res, n, m):
# Sorting a[] and b[]
a.sort()
b.sort()
# Merge two sorted arrays into res[]
i, j, k = 0, 0, 0
while (i < n and j < m):
if (a[i] <= b[j]):
res[k] = a[i]
i += 1
k += 1
else:
res[k] = b[j]
j += 1
k += 1
while (i < n): # Merging remaining
# elements of a[] (if any)
res[k] = a[i]
i += 1
k += 1
while (j < m): # Merging remaining
# elements of b[] (if any)
res[k] = b[j]
j += 1
k += 1
# Driver code
a = [ 10, 5, 15 ]
b = [ 20, 3, 2, 12 ]
n = len(a)
m = len(b)
# Final merge list
res = [0 for i in range(n + m)]
sortedMerge(a, b, res, n, m)
print "Sorted merged list :"
for i in range(n + m):
print res[i],
# This code is contributed by Sachin Bisht
C
// C# Code for Merging two unsorted
// arrays in sorted order
using System;
class GFG {
// Function to merge array in
// sorted order
static void sortedMerge(int []a, int []b,
int []res, int n, int m)
{
// Sorting a[] and b[]
Array.Sort(a);
Array.Sort(b);
// Merge two sorted arrays into res[]
int i = 0, j = 0, k = 0;
while (i < n && j < m)
{
if (a[i] <= b[j])
{
res[k] = a[i];
i += 1;
k += 1;
}
else
{
res[k] = b[j];
j += 1;
k += 1;
}
}
while (i < n)
{
// Merging remaining
// elements of a[] (if any)
res[k] = a[i];
i += 1;
k += 1;
}
while (j < m)
{
// Merging remaining
// elements of b[] (if any)
res[k] = b[j];
j += 1;
k += 1;
}
}
/* Driver program to test
above function */
public static void Main()
{
int []a = { 10, 5, 15 };
int []b = { 20, 3, 2, 12 };
int n = a.Length;
int m = b.Length;
// Final merge list
int []res = new int[n + m];
sortedMerge(a, b, res, n, m);
Console.Write( "Sorted merged list :");
for (int i = 0; i < n + m; i++)
Console.Write(" " + res[i]);
}
}
// This code is contributed by nitin mittal.
Output :
Sorted merge list : 2 3 5 10 12 15 20
时间复杂度：O(nlogn + mlogm +(n + m))。
空间复杂度： O((n + m))。
从上述时间复杂度显而易见，方法 2 优于方法 1。
版权属于：月萌API www.moonapi.com，转载请注明出处
