阳光家园广州网站网址,怎么快速优化网站,广告公司名字大全最新,吾爱网站0. 简介 归并排序#xff08;Merge Sort#xff09;是一种分治思想的应用#xff0c;它将待排序的数组不断拆分成小数组#xff0c;直到每个小数组只有一个元素#xff0c;然后将小数组两两合并#xff0c;直到最终得到有序的数组。 1. 归并排序的实现
归并排序的基本思…0. 简介 归并排序Merge Sort是一种分治思想的应用它将待排序的数组不断拆分成小数组直到每个小数组只有一个元素然后将小数组两两合并直到最终得到有序的数组。 1. 归并排序的实现
归并排序的基本思想
分解将待排序的数组从中间分成两部分递归地对左右两部分进行分解直到每个小数组只有一个元素这时可以认为每个小数组是有序的。解决将两个有序的小数组合并成一个有序的数组。可以使用双指针法比较两个数组的元素大小按照从小到大的顺序将元素放入新的数组中。合并递归地将左右两个有序的数组合并成一个更大的有序数组直到最终得到整个有序数组。
归并排序过程演示 2. 归并排序时空间复杂度分析
归并排序的时间复杂度和空间复杂度分析如下 时间复杂度 归并排序的时间复杂度是 O(n log n)其中 n 是待排序数组的长度。这是因为归并排序采用分治策略每次将数组分成两半进行递归排序然后再合并。在每一层递归中需要对所有元素进行比较和移动所以每层的时间复杂度是 O(n)。由于递归的深度是 log n因此总的时间复杂度是 O(n log n)。 空间复杂度 归并排序的空间复杂度是 O(n)。这是因为在合并过程中需要创建一个临时数组来存储两个有序子数组的元素。临时数组的大小与原数组相同所以空间复杂度是 O(n)。需要注意的是这个空间复杂度是额外的空间不包括递归调用所使用的栈空间。如果考虑递归调用的栈空间最坏情况下的空间复杂度将达到 O(n log n)。
综上所述归并排序的时间复杂度是 O(n log n)空间复杂度是 O(n)。 3. 归并排序C语言代码
C代码实现
#include stdio.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]; // 将数据拷贝到临时数组 for (i 0; i n1; i) L[i] arr[l i]; for (j 0; j n2; j) R[j] arr[m 1 j]; // 合并临时数组到原数组 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; }
} // 归并排序函数
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); // 合并左右两部分 }
} // 测试代码
int main() { int arr[] { 12, 11, 13, 5, 6, 7 }; int arr_size sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, arr_size - 1); // 对数组进行归并排序 printf(Sorted array:\n); for (int i 0; i arr_size; i) { printf(%d , arr[i]); } printf(\n); return 0;
}
代码解释
merge 函数
int n1 m - l 1; 和 int n2 r - m;这两行代码计算两个子数组的长度。n1 是左子数组的长度n2 是右子数组的长度。int L[n1], R[n2];我们创建两个临时数组 L 和 R 来存储左子数组和右子数组的元素。接下来的两个循环将左子数组和右子数组的元素拷贝到临时数组 L 和 R 中。然后我们使用三个指针 i, j, 和 k 来合并这两个有序的子数组。指针 i 和 j 分别指向临时数组 L 和 R 的当前元素而指针 k 指向原数组 arr 的当前位置。在合并的过程中我们比较 L[i] 和 R[j] 的值并将较小的元素放入原数组 arr 中。这个过程会一直持续到我们遍历完 L 或 R 中的所有元素。最后我们将剩余的元素如果有的话从 L 或 R 拷贝到原数组 arr 中。
mergeSort 函数
if (l r) { ... }这个条件用于判断数组是否至少包含两个元素。如果只有一个元素或没有元素那么数组已经是有序的不需要进一步排序。int m l (r - l) / 2;这行代码计算数组的中间位置。我们通过将数组的长度 (r - l) 除以 2 并加上起始索引 l 来得到中间位置 m。mergeSort(arr, l, m); 和 mergeSort(arr, m 1, r);这两行代码递归地对左子数组和右子数组进行排序。递归的终止条件是子数组的长度为 1 或 0。merge(arr, l, m, r);当左子数组和右子数组都被排序后我们使用 merge 函数将它们合并成一个有序的数组。 4. 归并排序代码运行结果
代码运行结果
