归并排序即其优化
⼀，概要
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法，该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路。
⼆，基本思想：
⾸先给⼀个数组⽤（arr来表⽰）：
下⼀步：将原数组分组，
第⼀次分：5,2,7,4⼀组，8,1,6,3，⼀组
第⼆次分组：5,2,⼀组，7,4⼀组，8,1⼀组，6,3⼀组
第三次分组：每个数各为⼀组
第⼆步：开始归并
第⼀次归并：5，与2原来是⼀组的，所以5和2对⽐，其他依次进⾏
第⼆次归并：
第三次归并：
就以第三次归并来讲下归并的⽅法：
（经过第⼀，⼆次归并后，arr={2,4,5,7,1,3,6,8}），由于第⼀，⼆次不⼤好说，所以这⾥从第三次归并开始，
第三次归并后有两组：
第⼀组（也就是3]表⽰）：
第⼀组（也就是7]表⽰）：
第⼀步：定义⼀个临时数组，长度为这两组的长度之和，这⾥命令为temp[8]，并将此时经过第⼀，⼆次归并得到的数组赋值给temp（即此时temp=
sort命令排序
{2,4,5,7,1,3,6,8}）;
第⼆步：⽤两个变量来代表这两个分组数组的第⼀个元素，这⾥⽤i,j;，从i=0,j=mid+1=4;(mid=(7-0)/2开始，
第三步：开始⽐较两组，
1，第⼀组的第⼀个元素arr[i]=2，与第⼆组的第⼀个元素arr[j]=1，⽐较，1<2，所以1应该放在数组arr的第⼀个位置，arr[k]=temp[j]，此时,k++,j++，2，继续⽐较，arr[i]=2与arr[j]=3，显然2<3；所以2放在数组arr的第⼆个位置arr[k]=temp[i]，此时k++,i++;
3,arr[i]=4与arr[j]=3，显然3<4；所以3放在数组arr的第三个位置arr[k]=temp[j]，此时k++,j++，
4，arr[i]=4与arr[j]=6，显然4<6；所以4放在数组arr的第四个位置arr[k]=temp[i]，此时k++,i++，
5，arr[i]=5与arr[j]=6，显然5<6；所以5放在数组arr的第五个位置arr[k]=temp[i]，此时k++,i++，
6,arr[i]=7与arr[j]=6，显然6<7；所以6放在数组arr的第六个位置arr[k]=temp[j]，此时k++,j++，
7，arr[i]=7与arr[j]=8，显然7<8；所以7放在数组arr的第七个位置arr[k]=temp[i]，此时k++,i++，
此时i++>mid了（即已经遍历玩第⼀组了，那就直接arr[k]=temp[j]了）；
到最后就可以完成排序了！（注意判断i,j是否合法）。
注意：上述是从第三次归并开始说的，可以观察到这两组已经是排好序的，当分组的时候⼀直往下分，到最后只有⼀个元素是⼀组，当然也就是有序的了，所以从最后⼀组开始归并，没完成⼀次，都会得到有序的分组，并在此基础上继续归并，这也验证了归并排序，是将已有序的⼦序列进⾏合并。
三，代码：
#include<iostream>
using namespace std;
//将id]和arr[]两部分进⾏归并
void __merge(int  arr[], int l, int mid, int r) {
//复制数组
int *temp = new int[r - l + 1];
for (int i = l; i <= r; i++)
temp[i - l] = arr[i];
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
//判断i是否有效
arr[k] = temp[j - l];
j++;
}
else if (j > r)
{
//判断j是否有效
arr[k] = temp[i - l];
i++;
}
else if (temp[i - l] < temp[j - l]) {
arr[k] = temp[i - l];
i++;
}
else {
arr[k] = temp[j - l];
j++;
}
}
}
void __mergesort(int arr[], int l, int r) {
if (l >= r)
return;
int mid = (l + r) / 2;
//分组
__mergesort(arr, l, mid);
__mergesort(arr, mid + 1, r);
//归并
__merge(arr, l, mid, r);
}
int main() {
int arr[8] = { 5,2,7,4,8,1,6,3 };
for (int i=0; i < 8; i++)
cout << arr[i] << " ";
__mergesort(arr, 0, 7);
cout << endl;
for (int i=0; i < 8; i++)
cout << arr[i] << " ";
return 0;
}
结果：
四，优化：
假如有如下情况：
假设经过第⼀次归并后，发现2,4这与5,7这组应⽤是按顺序排好的了，那就没有必要再对2,4,5,7进⾏归并了，具体做法如下：判断：arr[mid]<arr[mid+1]，成⽴则就不⽤进⾏归并，反之则进⾏，⽐如对于2,4,5,7这组，mid=（3-0）/2=1;
arr[mid]=4<arr[mid+1]=5;
代码：在上述代码的__mergesort中在进⾏归并前加上条件arr[mid]>arr[mid+1]。
void __mergesort(int arr[], int l, int r) {
if (l >= r)
return;
int mid = (l + r) / 2;
//分组
__mergesort(arr, l, mid);
__mergesort(arr, mid + 1, r);
//优化
if(arr[mid]>arr[mid+1])
__merge(arr, l, mid, r);
}
优化之后的对⽐：
关于对⽐⽅法，。
这⾥⽤1000000数据量进⾏对⽐：
对⽐后结果：
其实差别也不⼤！
五，总结
归并排序是稳定排序，它也是⼀种⼗分⾼效的排序，能利⽤完全⼆叉树特性的排序⼀般性能都不会太差。java中Arrays.sort()采⽤了⼀种名为TimSort的排序算法，就是归并排序的优化版本。从上⽂的图中可看出，每次合并操作的平均时间复杂度为O(n)，⽽完全⼆叉树的深度
为|log2n|。总的平均时间复杂度为O(nlogn)。⽽且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
认真领悟！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。