并归排序
并归排序是将两个有序的子序列和并得到一个完整的有序子序列,通过分治法将序列分成多个子序列进行并归排序 ,速度仅仅次与快速排序,为稳定排序算法,一般对总体无序,但是各个子项相对有序的数列
时间复杂度
平均时间复杂度O(nlogn)
最佳时间复杂度O(n)
基本思想
- 分解: 将n个元素分解成含n/2个元素的子序列
- 合并: 用合并排序法对两个子序列进行排序
动图演示
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| #include<bits/stdc++.h> using namespace std; void merge(int arr[],int L,int M,int R){ int leftSize=M-L; int rightSize=R-M+1; int left[leftSize]; int right[rightSize]; for(int i=L;i<M;i++){ left[i-L]=arr[i]; } for(int i=M;i<=R;i++){ right[i-M]=arr[i]; } int i=0,j=0,k=L; while(i<leftSize&&j<rightSize){ if(left[i]>right[j]){ arr[k]=right[j]; k++; j++; }else{ arr[k]=left[i]; k++; i++; } } while(i<leftSize){ arr[k]=left[i]; k++; i++; } while(j<rightSize){ arr[k]=right[j]; j++; k++; } } void mergeSort(int arr[],int L,int R){ if(L==R){ return ; }else{ int M=(L+R)/2; mergeSort(arr,L,M); mergeSort(arr,M+1,R); merge(arr,L,M+1,R); } } int main(){
int arr[]={8,2,5,3,6,1,7,4}; int arr2[]={2,5,6,8,1,3,4,7}; mergeSort(arr,0,7); for(int i=0;i<8;i++){ printf("%d ",arr[i]); }
return 0; }
|