黄冈网站建设优化排名_海南短视频搜索seo哪家实惠_小网站怎么搜关键词_百度关键词优化是什么意思

归并排序是分治法的典型应用，把两个或k个有序的子序列合并为一个。2路归并，2合一。k路归并，k合一。内部排序通常采用2路归并排序，先将数组分成两半，分别排序，然后合并。合并的过程需要将两个有序的子数组合并成一个有序的数组。

递归代码实现：

//A[left...mid]和A[mid+1...right]这两个部分各自有序，本函数的作用是将两个部分归并
//B是辅助数组，其元素个数和元素内容与待归并数组A相同
void Merge(int A[],int left,int mid,int right,int B[]){int i = left;int j = mid+1;int k = left;while(i <= mid && j <= right){if(A[i]<=A[j])//A[i]和A[j]相等的情况，把A[i]赋给B[k]，确保算法稳定性B[k++] = A[i++];elseB[k++] = A[j++];}while(i <= mid)   B[k++] = A[i++];while(j <= right) B[k++] = A[j++];//将归并后的数组B转存到A中for(int p = left;p <=right;p++) A[p] = B[p];
}//对数组A的[left...right]部分归并排序
//B是辅助数组，其元素个数和元素内容与待归并数组A相同
void MergeSort(int A[],int left,int right,int B[]){if(left < right){// 当 left 和 right 的值较大时（例如接近 INT_MAX），left + right 可能导致整数溢出。// int mid = (left + right) /2;   int mid = left + (right - left)/2;//避免整数溢出MergeSort(A,left,mid,B);    //对左半部分归并排序MergeSort(A,mid+1,right,B); //对右半部分归并排序Merge(A,left,mid,right,B);  //归并}
}

 n个元素进行2路归并排序，归并趟数=向上取整(log2n)。

每一趟归并时间复杂度是O(n)。

算法时间复杂度是O(nlog2n)。

2路归并排序性质

时间复杂度	O(nlogn)
空间复杂度	O(n)大小为n的辅助数组
稳定性	稳定
适用性	顺序表、链表