首页 > 代码库 > 归并排序（merge-sort）
归并排序（merge-sort）
一，归并排序
归并排序是建立在归并操作上的一种排序算法，它采用了分治法的思想，是一种稳定的排序算法，而且归并排序的速度仅次
于快速排序。时间复杂度：O（n*logn），最坏的情况：O（n*logn），空间复杂度：O(n)。从数据就可以看出：归并排序比快速
排序快很多，同样为稳定排序。
算法的思想：将一个无序的数组不断的分解成2个一组进行比较大小，并将比较后的部分数组按一定的顺序排放好。然后再继续将数组一部分进行比较，这样就可以了直至成为一个完整的数组。
例子： 6 2 4 7 3 8
第一趟排序： 2 6 4 3 7 8
第二趟排序： 2 4 6 3 7 8
第三趟排序： 2 3 4 6 7 8
示例代码：
#include <stdio.h>void Merge(int arrayA[], int first, int mid, int last, int arrayB[]) //将分解的数组进行归并{ int n = mid, m = last; int i = first, j = mid+1; int k = 0; while(i<=n && j<=m) //进行归并操作 { if(arrayA[i] <= arrayA[j]) arrayB[k++] = arrayA[i++]; else arrayB[k++] = arrayA[j++]; } while(i<=n) { arrayB[k++] = arrayA[i++]; } while(j<=m) { arrayB[k++] = arrayA[j++]; } for(i = 0; i<k; i++) //将归并好的数组按照一定的次序放回原来的数组 arrayA[first+i] = arrayB[i];}void MergeSort(int arrayA[], int first, int last, int arrayB[]) //将数组进行分解操作{ if(first < last) { int mid = (first+last)/2; MergeSort(arrayA, first, mid, arrayB); MergeSort(arrayA, mid+1, last, arrayB); Merge(arrayA, first, mid, last, arrayB); }}int main(){ int n; int arrayA[100], arrayB[100]; printf("请输入要排序数组的大小："); scanf("%d", &n); printf("请输入数组中各个数："); for(int i = 0; i<n; i++) scanf("%d", &arrayA[i]); MergeSort(arrayA, 0, n-1, arrayB); for(int i = 0; i<n; i++) printf("%d ",arrayB[i]); printf("\n"); for(int i = 0; i<n; i++) printf("%d ",arrayA[i]);}
二，用插入排序来优化归并排序
归并排序可以使得效率达到O(n*logn)，但我们可以利用插入排序将归并排序进一步优化，优化后的时间复杂度
为：O(n*log(n/k))，k的取值范围为：10到20左右，就是将数组切分成小于10个数来进行插入排序，这样可以进一步
减短归并排序的开销。因为在插入排序中，当n比较小时速度还是很快的。
优化后的代码：
#include <stdio.h>void Merge(int arrayA[], int first, int mid, int last, int arrayB[]) //将排序好的部分数组进行归并{ int n = mid, m = last; int i = first, j = mid+1; int k = 0; while(i<=n && j<=m) { if(arrayA[i] <= arrayA[j]) arrayB[k++] = arrayA[i++]; else arrayB[k++] = arrayA[j++]; } while(i<=n) { arrayB[k++] = arrayA[i++]; } while(j<=m) { arrayB[k++] = arrayA[j++]; } for(i = 0; i<k; i++) arrayA[first+i] = arrayB[i];}void InsertionSort(int arrayA[], int first, int last) //进行插入排序操作{ int mark; int i, j; for(i = first+1; i<=last; i++) { mark = arrayA[i]; j = i-1; while(j>=first && mark<arrayA[j]) { arrayA[j+1] = arrayA[j]; j--; } arrayA[j+1] = mark; }}void MergeSort(int arrayA[], int first, int last, int arrayB[]) //将数组进行分割，分割成每一块小于10个数{ if((last-first)>10) //若大于10个数则进行分割 { int mid = (first+last)/2; MergeSort(arrayA, first, mid, arrayB); MergeSort(arrayA, mid+1, last, arrayB); Merge(arrayA, first, mid, last, arrayB); } else //若小于10个数则进行插入排序 { InsertionSort(arrayA, first, last); }}int main(){ int n; int arrayA[100], arrayB[100]; printf("请输入要排序数组的大小："); scanf("%d", &n); printf("请输入数组中的各个数："); for(int i = 0; i<n; i++) scanf("%d", &arrayA[i]); MergeSort(arrayA, 0, n-1, arrayB); for(int i = 0; i<n; i++) printf("%d ", arrayA[i]); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。