按排序順序合并兩個未排序的數組 · 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。