归并排序,一种比较排序,通过对数组中的元素进行比较得出排序结果。
时间复杂度 O(nlogn)
,
空间复杂度O(n) +O(logn)
排序时间与输入无关,最佳情况,最坏情况都是如此, 稳定。
原理:
可以将数组分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序
核心算法(仅供参考):
void merge(int unsorted[], int first, int mid, int last, int sorted[])
{
int i = first, j = mid;
int k = 0;
while (i < mid && j < last)
if (unsorted[i] < unsorted[j])
sorted[k++] = unsorted[i++];
else
sorted[k++] = unsorted[j++];
while (i < mid)
sorted[k++] = unsorted[i++];
while (j < last)
sorted[k++] = unsorted[j++];
for (int v = 0; v < k; v++)
unsorted[first + v] = sorted[v];
}
void MergeSort(int arry[],int start,int end,int sorted[])
{
if(start<end)
{
int mid=(start+end)/2;//数组中点
MergeSort(arry,start,mid,sorted);//递归,排序前半段
MergeSort(arry,mid+1,end,sorted);//递归,排序后半段
merge(arry,start,mid,end,sorted);//归并。
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)