归并排序
时间: 2023-06-28 11:10:07 浏览: 35
归并排序是一种基于分治思想的排序算法。它的基本思想是将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些子序列合并成一个有序的序列。
具体来说,归并排序的过程可以描述为:
1. 将待排序序列平均分成两部分;
2. 对左右两部分分别进行归并排序,直到每个部分只有一个元素;
3. 将两个有序子序列合并成一个有序序列。
归并排序的代码实现如下:
```
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
}
void merge(int arr[], int l, int mid, int r) {
int n1 = mid - l + 1;
int n2 = r - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int 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++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
```
归并排序的时间复杂度为 O(nlogn),空间复杂度为 O(n)。由于归并排序需要额外的空间来存储临时数组,在实际应用中可能会受到限制。