按排序顺序合并两个未排序的数组 · GeeksForGeeks 中文系列教程

# 按排序顺序合并两个未排序的数组 > 原文： [https://www.geeksforgeeks.org/merging-two-unsorted-arrays-sorted-order/](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 // 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 // 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# ```cs // 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 // 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 // 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** 。本文由 [**Sachin Bisht**](https://www.linkedin.com/in/sachin-bisht-984b5013a/) 贡献。如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。