做企业网站的研究现状,hexo做网站,可以免费投放广告的平台,类似 wordpress基本思想
基本思想#xff1a;
归并排序#xff08;MERGE-SORT#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法#xff08;Divide and Conquer#xff09;的一个非常典型的应用。将已有序的子序列合并#xff0c;得到完全有序的序列#xff1…基本思想
基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
核心步骤
归并排序动图https://pic3.zhimg.com/v2-cdda3f11c6efbc01577f5c29a9066772_b.webp
先分割再归并 数组的左边有序右边也有序那么怎么数组整体有序呢取小的尾插到新数组
代码示例
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);//归并int begin1 begin, end1 mid;//左区间int begin2 mid 1, end2 end;//右区间int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}while (begin1 end1)tmp[i] a[begin1];while (begin2 end2)tmp[i] a[begin2];memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定
