C++ 与 Python 使用归并排序对数组进行排序的全新方法

点击上方蓝字 ● 关注Linux公社

归并排序是一种基于“分而治之”技术的排序算法。它是最有效的排序算法之一。

在本文中，您将了解归并排序算法的工作原理、归并排序算法、它的时间和空间复杂度，以及它在 C++、Python 和 JavaScript 等各种编程语言中的实现。

归并排序(Merge Sort)算法如何工作？

归并排序的工作原理是分而治之。合并排序重复地将一个数组分解为两个相等的子数组，直到每个子数组包含一个元素。最后，合并所有这些子数组，以便对结果数组进行排序。

借助示例可以更有效地解释这个概念。考虑具有以下元素的未排序数组：{16, 12, 15, 13, 19, 17, 11, 18}。

在这里，归并排序算法将数组分成两半，为这两半调用自身，然后将排序后的两半合并。

归并排序算法

下面是归并排序的算法：


MergeSort(arr[], leftIndex, rightIndex)if leftIndex >= rightIndex     returnelse     Find the middle index that divides the array into two halves:               middleIndex = leftIndex + (rightIndex-leftIndex)/2     Call mergeSort() for the first half:                Call mergeSort(arr, leftIndex, middleIndex)     Call mergeSort() for the second half:             Call mergeSort(arr, middleIndex+1, rightIndex)     Merge the two halves sorted in step 2 and 3:             Call merge(arr, leftIndex, middleIndex, rightIndex)

归并排序算法的时空复杂度

归并排序算法可以表示为以下递推关系的形式：

T(n) = 2T(n/2) + O(n)

使用主定理或递归树方法求解此递归关系后，您将得到 O(n logn) 的解。因此，归并排序算法的时间复杂度为O(n logn)。

合并排序的最佳情况时间复杂度： O(n logn)

归并排序的平均时间复杂度： O(n logn)

归并排序的最坏情况时间复杂度： O(n logn)

归并排序算法的辅助空间复杂度为O(n)，因为在归并排序实现中需要n 个 辅助空间。

归并排序算法的 C++ 实现

下面是归并排序算法的 C++ 实现：


// C++ implementation of the// merge sort algorithm#include using namespace std;// This function merges two subarrays of arr[]// Left subarray: arr[leftIndex..middleIndex]// Right subarray: arr[middleIndex+1..rightIndex]void merge(int arr[], int leftIndex, int middleIndex, int rightIndex){ int leftSubarraySize = middleIndex - leftIndex + 1; int rightSubarraySize = rightIndex - middleIndex;// Create temporary arrays int L[leftSubarraySize], R[rightSubarraySize];// Copying data to temporary arrays L[] and R[] for (int i = 0; i < leftSubarraySize; i++) L[i] = arr[leftIndex + i];


    
 for (int j = 0; j < rightSubarraySize; j++) R[j] = arr[middleIndex + 1 + j];// Merge the temporary arrays back into arr[leftIndex..rightIndex]// Initial index of Left subarray int i = 0;// Initial index of Right subarray int j = 0;// Initial index of merged subarray int k = leftIndex;while (i < leftSubarraySize && j < rightSubarraySize) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; }// If there're some remaining elements in L[]// Copy to arr[] while (i < leftSubarraySize) { arr[k] = L[i]; i++; k++; }// If there're some remaining elements in R[]// Copy to arr[] while (j < rightSubarraySize) { arr[k] = R[j]; j++; k++; }}void mergeSort(int arr[], int leftIndex, int rightIndex){ if(leftIndex >= rightIndex) { return; } int middleIndex = leftIndex + (rightIndex - leftIndex)/2; mergeSort(arr, leftIndex, middleIndex); mergeSort(arr, middleIndex+1, rightIndex); merge(arr, leftIndex, middleIndex, rightIndex);}
// Function to print the elements// of the arrayvoid printArray(int arr[], int size){ for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl;}// Driver codeint main(){ int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 }; int size = sizeof(arr) / sizeof(arr[0]);cout << "Unsorted array:" << endl; printArray(arr, size);mergeSort(arr, 0, size - 1);cout << "Sorted array:" << endl; printArray(arr, size);return 0;}

输出：


Unsorted array:16 12 15 13 19 17 11 18 Sorted array:11 12 13 15 16 17 18 19

归并排序算法的 JavaScript 实现

下面是合并排序算法的 JavaScript 实现：


// JavaScript implementation of the// merge sort algorithm// This function merges two subarrays of arr[]// Left subarray: arr[leftIndex..middleIndex]// Right subarray: arr[middleIndex+1..rightIndex]function merge(arr, leftIndex, middleIndex, rightIndex) { let leftSubarraySize = middleIndex - leftIndex + 1; let rightSubarraySize = rightIndex - middleIndex;// Create temporary arrays var L = new Array(leftSubarraySize); var R = new Array(rightSubarraySize);// Copying data to temporary arrays L[] and R[] for(let i = 0; i L[i] = arr[leftIndex + i]; } for (let j = 0; j R[j] = arr[middleIndex + 1 + j]; }// Merge the temporary arrays back into arr[leftIndex..rightIndex]// Initial index of Left subarray var i = 0;// Initial index of Right subarray var j = 0;// Initial index of merged subarray var k = leftIndex;while (i < leftSubarraySize && j < rightSubarraySize) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; }// If there're some remaining elements in L[]// Copy to arr[] while (i < leftSubarraySize) { arr[k] = L[i]; i++; k++; }// If there're some remaining elements in R[]// Copy to arr[] while (j < rightSubarraySize) { arr[k] = R[j]; j++; k++; }}function mergeSort(arr, leftIndex, rightIndex) { if(leftIndex >= rightIndex) { return } var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2); mergeSort(arr, leftIndex, middleIndex); mergeSort(arr, middleIndex+1, rightIndex); merge(arr, leftIndex, middleIndex, rightIndex);}// Function to print the elements// of the arrayfunction printArray(arr, size) { for(let i = 0; i document.write(arr[i] + " "); } document.write("
");}// Driver code:var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];var size = arr.length;document


    
.write("Unsorted array:
");printArray(arr, size);mergeSort(arr, 0, size - 1);document.write("Sorted array:
");printArray(arr, size);

输出：


Unsorted array:16 12 15 13 19 17 11 18Sorted array:11 12 13 15 16 17 18 19

归并排序算法的 Python 实现

下面是归并排序算法的 Python 实现：


# Python implementation of the# merge sort algorithmdef mergeSort(arr):    if len(arr) > 1:        # Finding the middle index of the array        middleIndex = len(arr)//2        # Left half of the array        L = arr[:middleIndex]        # Right half of the array        R = arr[middleIndex:]        # Sorting the first half of the array        mergeSort(L)        # Sorting the second half of the array        mergeSort(R)        # Initial index of Left subarray        i = 0        # Initial index of Right subarray        j = 0        # Initial index of merged subarray        k = 0        # Copy data to temp arrays L[] and R[]        while i < len(L) and j < len(R):            if L[i] < R[j]:                arr[k] = L[i]                i = i + 1            else:                arr[k] = R[j]                j = j + 1            k = k + 1        # Checking if there're some remaining elements        while i < len(L):            arr[k] = L[i]            i = i + 1            k = k + 1        while j < len(R):            arr[k] = R[j]            j = j + 1            k = k + 1# Function to print the elements# of the arraydef printArray(arr, size):    for i in range(size):        print(arr[i], end=" ")    print()
# Driver codearr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]size = len(arr)print("Unsorted array:")printArray(arr, size)mergeSort(arr)print("Sorted array:")printArray(arr, size)

输出：


Unsorted array:16 12 15 13 19 17 11 18Sorted array:11 12 13 15 16 17 18 19

了解其他排序算法

排序是编程中最常用的算法之一。您可以使用各种排序算法（如快速排序、冒泡排序、归并排序、插入排序等）对不同编程语言中的元素进行排序。

如果您想了解最简单的排序算法，冒泡排序是最佳选择。

来自：Linux迷
链接：https://www.linuxmi.com/merge-sort-python-c.html

关注我们

长按或扫描下面二维码关注 Linux公社

关注 Linux公社，添加“ 星标 ”

每天获取技术干货，让我们一起成长

合作联系： root@linuxidc.net