1.归并排序
归并排序采用的思想是分而治之,简单来说,就是将一个待排序的序列,不断划分,最终得到有序的序列(只剩一个元素的序列就是有序序列),然后将这些有序的序列进行合并,第一次合并将只有一个元素序列的有序子序列进行合并,就会得到有两个元素序列的有序子序列,然后进行第二次合并,将有两个元素序列的有序序列进行合并,就会得到有四个元素序列的有序序列,如此下去,直到全部元素有序。
举个例子就会一目了然:
待排序序列:1 -9 3 8 6 2 3 -1
第一次划分:1 -9 3 8 6 2 3 -1 得到两个序列
第二次划分:1 -9 3 8 6 2 3 -1 得到四个序列
第三次划分 :1 -9 3 8 6 2 3 -1 得到8个序列,此时每个序列都是有序的,因为只有一个元素
合并
第一次合并:-9 1 3 8 2 6 -1 3 得到四个有序序列
第二次合并:-9 1 3 8 -1 2 3 6 得到两个有序序列
第三次合并:-9 -1 1 2 3 3 6 8 得到一个有序序列,排序完成。
2.步骤
1 #include<stdio.h> 2 void merge(int * arr,int left,int mid,int right) 3 { 4 int i=left;//左边子序列的起点 5 int j=mid+1;//右边子序列的起点 6 int temp[10];//暂时数组 7 int n=0;//本次合并元素的个数 8 9 //比较两个序列,将符合要求的元素放进temp数组 10 while(i<=mid&&mid<=right) 11 { 12 if(arr[i]<arr[j]) 13 temp[n++]=arr[i++]; 14 else 15 temp[n++]=arr[j++]; 16 } 17 //如果左边序列还有剩 18 while(i<mid) 19 temp[n++]=arr[i++]; 20 21 //如果有边序列还有剩 22 while(j<=right) 23 temp[n++]=arr[j++]; 24 25 //将排序好的元素放回原本数组对应的位置 26 for(i=0;i<n;i++) 27 arr[left++]=temp[i]; 28 } 29 void mergesort(int * arr,int left,int right) 30 { 31 32 if(left<right) 33 { 34 int mid=(left+right)/2;//分治 35 mergesort(arr,left,mid);//递归左边序列 36 mergesort(arr,mid+1,right);//递归右边序列 37 merge(arr,left,mid,right);//开始合并 38 } 39 40 } 41 int main() 42 { 43 int i; 44 int arr[10]={1,3,-9,0,10,2,8,9,19,-1}; 45 mergesort(arr,0,9);//归并排序 46 for(i=0;i<10;i++) 47 printf("%dn",arr[i]); 48 return 0; 49 }
结果:
归并排序的时间复杂度是:o(nlog₂n)是一种效率很高的算法,并且是稳定的排序算法。稳定是指在排序的时候,相等的元素不会进行交换。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599960.html