归并排序是什么?归并排序法原理以及代码实例讲解

思想:此处的归并排序为最基本的2-路归并排序,将序列分成若干组,组内排序完成后,再合并为一个有序序列。

原理:将序列两两分组,将序列归并为[n/2]个组,组内单独排序;然后将这些组再两两归并,生成[n/4]个组,组内再单独排序;以此类推,直到只剩下一个组为止。

代码描述:

#include<cstdio>
const int maxn = 100;
//将数组A的[L1,R1]和[L2,R2]区间合并为有序区间(此处L2即为R1+1)
void merge(int A[],int L1,int R1,int L2,int R2) {
int i=L1,j=L2; //i指向A[l1],j指向A[L2] int temp[maxn],index = 0; //temp临时存放合并后的数组,index为其下标
while(i<=R1&&j<=R2){
if(A[i]<=A[j]) { //如果A[i]<=A[j] temp[index++]=A[i++]; //将A[i]加入序列temp
}else{ // 如果A[i]>A[j] temp[index++]=A[j++]; //将A[j]加入序列temp
}
}
while(i<=R1) temp[index++] = A[i++]; //将[L1,R1]的剩余元素加入序列temp
while(j<=R2) temp[index++] = A[j++]; //将[L2,R2]的剩余元素加入序列temp
for(i=0;i<index;i++){
A[L1+i] = temp[i]; //将合并后的序列赋值回数组A
}
}

//将array数组当前区间[left,right]进行归并排序
void mergeSort(int A[],int left,int right) {
if(left<right){ //只要left<right
int mid = (left+right)/2; //取[left,right]的中点
mergeSort(A,left,mid); //递归,将左子区间[left,mid]归并排序
mergeSort(A,mid+1,right); //递归,将右子区间[mid+1,right]归并排序
merge(A,left,mid,mid+1,right); //将左子区间和右子区间合并
}
}
int main(){
const int n=10;
int A[n] = {1,2,4,5,6,43,7,9,3,5};
mergeSort(A,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",A[i]);
}
return 0;
}

分析:其核心在于如何将两个有序序列合并成一个有序序列。

时间复杂度:O(nlogn)

空间复杂度:O(n)

相关推荐

剑指Offer(Python多种思路实现):合并两个排序的链表

【Python学习1:爬取百度贴吧并按回复量生成排序】

【Python学习1:爬取百度贴吧并按回复量生成排序】

C++类对象排序operator重载操作

快速排序找数组中的第N大数