稳定性：稳定排序
1.过程介绍
归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并，归并排序的算法效率仅次于快速排序，是一种稳定的算法，需要建立两倍的数组空间，一般用于对总体而言无序，但是各子项又相对有序【并不是完全乱序】的情况比较适用。
a)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
b)设定两个指针，最初位置分别为两个已经排序序列的起始位置
c)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤c直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
2.图示过程
第一次排序将数据分为“两个”一组，组内顺序，其次再逐个的将各组进行整合，最终完成归并排序
|
第一趟 |
50 |
70 |
20 |
30 |
10 |
70 |
40 |
60 |
|
第二趟 |
20 |
30 |
50 |
70 |
10 |
40 |
60 |
70 |
|
第三趟 |
10 |
20 |
30 |
40 |
50 |
60 |
70 |
70 |
|
第四趟 |
10 |
20 |
30 |
40 |
50 |
60 |
70 |
70 |
1 #include <iostream> 2 #include <math.h> 3 using namespace std; 4 5 void merge(int arr[],int l,int mid,int r) { 6 int aux[r-l+1];//开辟一个新的数组，将原数组映射进去 7 for(int m=l; m<=r; m++) { 8 aux[m-l]=arr[m]; 9 } 10 11 int i=l,j=mid+1;//i和j分别指向两个子数组开头部分 12 13 for(int k=l; k<=r; k++) { 14 if(i>mid) { 15 arr[k]=aux[j-l]; 16 j++; 17 } else if(j>r) { 18 arr[k]=aux[i-l]; 19 i++; 20 } else if(aux[i-l]<aux[j-l]) { 21 arr[k]=aux[i-l]; 22 i++; 23 } else { 24 arr[k]=aux[j-l]; 25 j++; 26 } 27 } 28 } 29 30 void merge_sort(int arr[],int n) { 31 for(int sz=1; sz<=n; sz+=sz) { 32 for(int i=0; i+sz<n; i+=sz+sz) { //i+sz防止越界 33 //对局部：arr[i...sz-1]和arr[i+sz.....i+2*sz-1]进行排序 34 merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1)); //min函数防止越界 35 } 36 } 37 38 } 39 40 int main() { 41 int a[8]= {70,50,30,20,10,70,40,60}; 42 int n=8; 43 merge_sort(a,n); 44 for(int i=0; i<n; i++) { 45 cout<<a[i]<<" "; 46 } 47 return 0; 48 }
输出：
1 10 20 30 40 50 60 70 70
原文：https://www.cnblogs.com/qunxuan/p/13219452.html