归并排序算法
归并排序是一种基于分治法的排序技术。其最坏情况时间复杂度为Ο(n log n)，是最常用和最容易实现的算法之一。
归并排序首先将数组分成相等的两半，然后按排序的方式将它们合并。
归并排序的工作原理？
为了理解归并排序，我们将一个未排序的数组视为如下的−
我们知道，归并排序首先会迭代地将整个数组分成相等的两半，除非达到原子值。我们在这里看到，一个包含 8 个元素的数组被分成两个大小为 4 的数组。
这不会改变原始数组中元素出现的顺序。现在我们将这两个数组分成两半。
我们进一步划分这些数组，得到了原子值，它不能再被分割了。
现在，我们按照与分解时完全相同的方式将它们合并。请注意这些列表的颜色代码。
我们首先比较每个列表的元素，然后将它们按排序方式组合成另一个列表。我们看到 14 和 33 处于排序位置。我们比较 27 和 10，在包含两个值的目标列表中，我们将 10 放在最前面，然后是 27。我们调整 19 和 35 的顺序，而 42 和 44 则按顺序排列。
在合并阶段的下一次迭代中，我们比较两个数据值的列表，并将它们合并成一个已找到数据值的列表，并将所有数据值按排序顺序排列。
最终合并后，列表将按排序顺序排列，并被视为最终解决方案。
归并排序算法
归并排序算法不断将列表分成相等的两半，直到无法再分割。根据定义，如果列表中只有一个元素，则认为该列表已排序。然后，归并排序算法将较小的已排序列表合并，使新列表也保持排序状态。
步骤 1：如果列表中只有一个元素，则认为它已排序， 因此返回。 步骤 2：递归地将列表分成两半，直到无法再分割。 步骤 3：将较小的列表按排序顺序合并为新列表。
伪代码
现在我们将看到归并排序函数的伪代码。正如我们的算法指出的两个主要函数 - 除法和合并。
合并排序与递归一起工作，我们将以相同的方式看到我们的实现。
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure
示例
在以下示例中，我们逐步演示了归并排序算法。首先，将每个迭代数组分成两个子数组，直到子数组只包含一个元素。当这些子数组无法进一步划分时，则执行合并操作。
分析
假设归并排序的运行时间为 T(n)。因此，
$$\mathrm{T\left ( n ight )=\left\{\begin{matrix} c & if\, n\leq 1 \ 2\, xT\left ( \frac{n}{2} ight )+dxn &otherwise \ \end{matrix} ight.}\:其中\: c\: 和\: d\: 为常数$$
因此，利用此递推关系，
$$T\left ( n ight )=2^{i}\, T\left ( n/2^{i} ight )+i\cdot d\cdot n$$
$$由于\:\: i=log\: n，\: T\left ( n ight )=2^{log\, n}T\left ( n/2^{log\, n} ight )+log\, n\cdot d\cdot n$$
$$=c\cdot n+d\cdot n\cdot log\: n$$
$$因此，\: \: T\left ( n ight ) = O(n\: log\: n ).$$
示例
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high){
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high){
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main(){
int i;
printf("Array before sorting
");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("
Array after sorting
");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
}
输出
Array before sorting 10 14 19 26 27 31 33 35 42 44 0 Array after sorting 0 10 14 19 26 27 31 33 35 42 44
#include <iostream>
using namespace std;
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high){
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high){
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main(){
int i;
cout << "Array before sorting
";
for(i = 0; i <= max; i++)
cout<<a[i]<<" ";
sort(0, max);
cout<< "
Array after sorting
";
for(i = 0; i <= max; i++)
cout<<a[i]<<" ";
}
输出
Array before sorting 10 14 19 26 27 31 33 35 42 44 0 Array after sorting 0 10 14 19 26 27 31 33 35 42 44
public class Merge_Sort {
static int a[] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
static int b[] = new int[a.length];
static void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
static void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
public static void main(String args[]) {
int i;
int n = a.length;
System.out.println("Array before sorting");
for(i = 0; i < n; i++)
System.out.print(a[i] + " ");
sort(0, n-1);
System.out.println("
Array after sorting");
for(i = 0; i < n; i++)
System.out.print(a[i]+" ");
}
}
输出
Array before sorting 10 14 19 26 27 31 33 35 42 44 0 Array after sorting 0 10 14 19 26 27 31 33 35 42 44
def merge_sort(a, n):
if n > 1:
m = n // 2
#divide the list in two sub lists
l1 = a[:m]
n1 = len(l1)
l2 = a[m:]
n2 = len(l2)
#recursively calling the function for sub lists
merge_sort(l1, n1)
merge_sort(l2, n2)
i = j = k = 0
while i < n1 and j < n2:
if l1[i] <= l2[j]:
a[k] = l1[i]
i = i + 1
else:
a[k] = l2[j]
j = j + 1
k = k + 1
while i < n1:
a[k] = l1[i]
i = i + 1
k = k + 1
while j < n2:
a[k]=l2[j]
j = j + 1
k = k + 1
a = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0]
n = len(a)
print("Array before Sorting")
print(a)
merge_sort(a, n)
print("Array after Sorting")
print(a)
输出
Array before Sorting [10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0] Array after Sorting [0, 10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
