归并排序
归并排序的python实现
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。
它将数组分成两个子数组，分别对子数组进行排序，然后合并两个有序的子数组。
算法步骤
- 递归分解数组，直到子数组的长度为1
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，初始位置分别为两个已经排序序列的起始位置
- 对比两个指针所指向的元素，选择相对小的元素放入到合并空间
- 移动指针，直到有一个序列的元素全部处理完毕
- 合并临时空间中的数据，到原数组中
- 释放临时空间
- 向上一层返回
CODE
Python
def merge_sort(arr):
def merge(left: int, right: int) -> None:
if left >= right:
return
mid = (left + right) // 2
merge(left, mid)
merge(mid + 1, right)
i, j = left, mid + 1
tmp = []
while i <= mid and j <= right:
if arr[i] < arr[j]:
tmp.append(arr[i])
i += 1
else:
tmp.append(arr[j])
j += 1
while i <= mid:
tmp.append(arr[i])
i += 1
while j <= right:
tmp.append(arr[j])
j += 1
arr[left:right+1] = tmp
merge(0, len(arr) - 1)Java
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
merge(arr, left, mid, right, temp);
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
System.arraycopy(temp, left, arr, left, right - left + 1);
}
}