点击上方蓝字 ● 关注Linux公社
归并排序是一种基于“分而治之”技术的排序算法。它是最有效的排序算法之一。在本文中,您将了解归并排序算法的工作原理、归并排序算法、它的时间和空间复杂度,以及它在 C++、Python 和 JavaScript 等各种编程语言中的实现。归并排序(Merge Sort)算法如何工作?
归并排序的工作原理是分而治之。合并排序重复地将一个数组分解为两个相等的子数组,直到每个子数组包含一个元素。最后,合并所有这些子数组,以便对结果数组进行排序。借助示例可以更有效地解释这个概念。考虑具有以下元素的未排序数组:{16, 12, 15, 13, 19, 17, 11, 18}。在这里,归并排序算法将数组分成两半,为这两半调用自身,然后将排序后的两半合并。归并排序算法
MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
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)
归并排序算法的时空复杂度
使用主定理或递归树方法求解此递归关系后,您将得到 O(n logn) 的解。因此,归并排序算法的时间复杂度为O(n logn)。合并排序的最佳情况时间复杂度: O(n logn)归并排序的最坏情况时间复杂度: O(n logn)归并排序算法的辅助空间复杂度为O(n),因为在归并排序实现中需要n 个 辅助空间。归并排序算法的 C++ 实现
#include
using namespace std;
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
int L[leftSubarraySize], R[rightSubarraySize];
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];
int i = 0;
int j = 0;
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++;
}
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
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);
}
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int 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 实现:
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
for(let i = 0; i
L[i] = arr[leftIndex + i];
}
for (let j = 0; j
R[j] = arr[middleIndex + 1 + j];
}
var i = 0;
var j = 0;
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++;
}
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
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 printArray(arr, size) {
for(let i = 0; i
document.write(arr[i] + " ");
}
document.write("
");
}
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 18
Sorted array:
11 12 13 15 16 17 18 19
归并排序算法的 Python 实现
def mergeSort(arr):
if len(arr) > 1:
middleIndex = len(arr)//2
L = arr[:middleIndex]
R = arr[middleIndex:]
mergeSort(L)
mergeSort(R)
i = 0
j = 0
k = 0
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
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
def printArray(arr, size):
for i in range(size):
print(arr[i], end=" ")
print()
arr = [ 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 18
Sorted array:
11 12 13 15 16 17 18 19
了解其他排序算法
排序是编程中最常用的算法之一。您可以使用各种排序算法(如快速排序、冒泡排序、归并排序、插入排序等)对不同编程语言中的元素进行排序。如果您想了解最简单的排序算法,冒泡排序是最佳选择。来自:Linux迷
链接:https://www.linuxmi.com/merge-sort-python-c.html
长按或扫描下面二维码关注
Linux公社
关注
Linux公社,添加“
星标
”
每天
获取
技术干货,让我们一起成长
合作联系:
root@linuxidc.net