归并排序是一种分而治之的算法。它基于以下思想:将未排序的数组划分为多个子数组，直到每个子数组由单个元素组成，然后以产生排序数组的方式合并这些子数组。归并排序的过程步骤可以概括如下:
- 划分: 将未排序的数组划分为多个子数组，直到每个子数组只包含单个元素。
- 合并:将子数组合并为有序数组，然后合并直至获得原始数组。
- 合并技术: 考虑并比较两个子数组的第一个元素。对于升序排序，从子数组中取出值较小的元素，并成为排序数组的新元素。重复此过程，直到两个子数组都被清空并且合并后的数组成为排序数组。
示例:
为了理解合并排序，让我们考虑一个未排序的数组[4, 9, -4]（下图中第 11 个过程后创建的右侧数组）并讨论按升序对数组进行排序所采取的每个步骤。
在第一步，将数组[4, 9, -4]分为两个子数组。第一个子数组包含 [4, 9]，第二个子数组包含 [-4]。由于第一个子数组中的元素数量大于1，因此将其进一步分为分别由元素[4]和[9]组成的子数组。由于所有子数组的元素个数均为 1，因此无法对数组进行进一步划分。
在合并过程中，将上一步形成的子数组合并在一起，使用上面提到的过程形成一个排序数组。首先，将[4]和[9]子数组合并在一起，形成排序子数组[4, 9]。然后将[4, 9]和[-4]子数组合并在一起形成最终的排序数组[-4, 4, 9]
归并排序的实现
public class MyClass {
// 合并排序函数 - 分割数组
//并调用merge函数对数组进行排序和合并
//归并排序是一个递归函数
static void mergesort(int Array[], int left, int right) {
if (left < right) {
int mid = left + (right - left)/2;
mergesort(Array, left, mid);
mergesort(Array, mid+1, right);
merge(Array, left, mid, right);
}
}
//合并函数执行排序和合并操作
//用于合并排序函数
static void merge(int Array[], int left, int mid, int right) {
// 创建两个临时数组来保存 split
//主数组的元素
int n1 = mid - left + 1; //LeftArray 中的元素数量
int n2 = right - mid; //RightArray 中的元素数量
int LeftArray[] = new int[n1];
int[] RightArray = new int [n2];
for(int i=0; i < n1; i++) {
LeftArray[i] = Array[left + i];
}
for(int i=0; i < n2; i++) {
RightArray[i] = Array[mid + i + 1];
}
//下面的x,y,z代表索引号
//分别为LeftArray、RightArray和Array
int x=0, y=0, z=left;
while(x < n1 && y < n2) {
if(LeftArray[x] < RightArray[y]) {
Array[z] = LeftArray[x];
x++;
}
else {
Array[z] = RightArray[y];
y++;
}
z++;
}
//复制LeftArray的剩余元素
while(x < n1) {
Array[z] = LeftArray[x];
x++;
z++;
}
//复制RightArray的剩余元素
while(y < n2) {
Array[z] = RightArray[y];
y++;
z++;
}
}
//打印数组的函数
static void PrintArray(int Array[]) {
int n = Array.length;
for (int i=0; i<n; i++)
System.out.print(Array[i] + " ");
System.out.println();
}
//测试代码
public static void main(String[] args) {
int[] MyArray = {10, 1, 23, 50, 4, 9, -4};
int n = MyArray.length;
System.out.println("原始数组");
PrintArray(MyArray);
mergesort(MyArray, 0, n-1);
System.out.println("\n排序数组");
PrintArray(MyArray);
}
} 上面的代码将给出以下输出:
原始数组
10 1 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
在所有情况下（最差、平均和最佳），合并排序始终划分数组，直到所有子数组都包含单个元素，并花费线性时间来合并这些子数组。划分过程的时间复杂度为θ(logN)，合并过程的时间复杂度为θ(N)。因此，在所有情况下，归并排序的时间复杂度都是θ(NlogN)。