归并排序 (Merge Sort)
归并排序是一种有效的排序算法，采用分治法的一个典型应用。它将数组分成两半，对每部分递归地应用归并排序，然后将排序后的部分合并。在处理大数据集时，归并排序特别有效，因为它的时间复杂度
python代码实现（带有随机数据）
data = [25, 57, 24, 66, 25, 19, 90, 84, 38, 80, 7, 33, 96, 71, 6, 99, 99, 29, 63, 65, 49, 75, 88, 90, 46, 53, 36, 55, 9, 42, 13, 3, 52, 31, 0, 71, 88, 89, 90, 10, 58, 49, 40, 62, 0, 81, 5, 93, 91, 97]
def merge_sort(arr):
if len(arr) > 1:
# 找到数组的中间点并分割成左右两部分
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
# 递归调用归并排序来分别排序左右两部分
merge_sort(L)
merge_sort(R)
i = j = k = 0
# 将数据从两个临时数组复制回原数组arr
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# 检查是否有剩余元素
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# 对数据进行归并排序
merge_sort(data)
print("排序后的数据:", data)
c代码实现
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组
int L[n1], R[n2];
// 拷贝数据到临时数组L[]和R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// 将临时数组的数据合并回arr[l..r]
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 拷贝L[]中的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 拷贝R[]中的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// 找到中间点
int m = l + (r - l) / 2;
// 分别对左半部和右半部进行归并排序
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// 合并两半
merge(arr, l, m, r);
}
}
/* 用于打印数组 */
void printArray(int A[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("
");
}
/* 测试归并排序程序 */
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("给定的数组是
");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("
排序后的数组是
");
printArray(arr, arr_size);
return 0;
}
具体实现步骤
以下是归并排序的具体步骤：
-
分割：首先将数组递归地分割成两半，直到每个子数组只有一个元素或为空。
-
合并：然后将这些子数组合并起来，形成一个有序的数组。
让我们更详细地分析这个过程：
分割步骤
- 开始时，你有一个未排序的数组。
- 将数组从中间分割成两部分，如果数组有奇数个元素，其中一个部分将多出一个元素。
- 对这两个子数组递归地执行相同的分割操作，直到每个子数组只包含一个元素或为空。这时，每个子数组都被认为是有序的。
合并步骤
- 一旦你有了一系列有序的子数组，你就开始将它们合并在一起，以形成更大的有序数组。
- 在合并过程中，你从两个子数组的起始位置开始，比较它们的元素。将较小的元素先放入新的数组中，然后移动到下一个元素。
- 如果一个子数组的所有元素都被选中了，而另一个子数组还有剩余元素，那么剩余的元素将直接被复制到新数组的末尾。
- 这个过程重复进行，直到所有的子数组都被合并成一个完整的、有序的数组。
归并排序的效率来自于它能够保持