归并排序

• 归并排序（Mergesort）的思想依然是分治（Divide and conquer），不过是先将一个数列分成子序列分别排序，再将排好序的子序列合并成一个有序序列，此过程称之为“归并 （merge）”
• 算法描述
  • 1.选取数列中的中间点为分界点，将n个元素分成两个分别含有n/2元素的子序列（如果n为奇数，则左边的元素比右边的元素多1）
  • 2.将两个子序列递归排序，直到整个序列被分成n个子序列
  • 3.从最底层开始逐步合并两个排好序的序列
• 时间复杂度 ：n log n

归并排序模板如下：

void merge_sort(int q[], int l, int r) // q[]为排序数组，l为左边界，r为有边界 {if (l >= r) return; // 如果数组中中只有0个或1个原则，不用排序int mid = l + r >> 1; // 取区间的中间值merge_sort(q, l, mid), merge_sort(q, mid + 1, r); // 递归排序左右子序列int k = 0, i = l, j = mid + 1; // k表示tmp数组中的个数，i是左子序列地起点，j为右子序列起点while (i <= mid && j <= r) // 左右子序列都非空if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; // 把左右子序列中较小的数放到当前位置上else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ]; // 将左右两个子序列没有遍历完的接到tmp数组上while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; // 把存在tmp数组中的结果赋值给q数组 }

总结

以上是生活随笔为你收集整理的归并排序（MergeSort）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。