榆林市横山县建设局官方网站,电视剧男女直接做视频网站,重庆建设空调网站,绵阳市公司网站建设文章目录 归并排序概念归并排序算法思路归并排序递归实现归并排序非递归实现 归并排序概念
1945年#xff0c;约翰冯诺依曼#xff08;John von Neumann#xff09;发明了归并排序#xff0c;这是典型的分治算法的应用。 归并排序#xff08;Merge sort#xff09;是建立… 文章目录 归并排序概念归并排序算法思路归并排序递归实现归并排序非递归实现 归并排序概念
1945年约翰·冯·诺依曼John von Neumann发明了归并排序这是典型的分治算法的应用。 归并排序Merge sort是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。 归并排序算法思路
归并排序算法有两个基本的操作一个是分也就是把原数组划分成两个子数组的过程。另一个是治它将两个有序数组合并成一个更大的有序数组。
1 将待排序的线性表不断地切分成若干个子表直到每个子表只包含一个元素这时可以认为只包含一个元素的子表是有序表。 2 将子表两两合并每合并一次就会产生一个新的且更长的有序表重复这一步骤直到最后只剩下一个子表这个子表就是排好序的线性表。
相信大家都知道如何将两个有序序列合为一个有序序列吧
那么如何得到有序的子序列呢当序列分解到只有一个元素或是没有元素时就可以认为是有序了这时分解就结束了开始合并
归并排序递归实现
归并排序从其思想上看就很适合使用递归来实现并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列合并完毕后再将数据拷贝回原数组。
代码示例
//归并排序子函数
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left right)//归并结束条件当只有一个数据或是序列不存在时不需要再分解{return;}int mid left (right - left) / 2;//中间下标_MergeSort(a, left, mid, tmp);//对左序列进行归并_MergeSort(a, mid 1, right, tmp);//对右序列进行归并int begin1 left, end1 mid;int begin2 mid 1, end2 right;//将两段子区间进行归并归并结果放在tmp中int i left;while (begin1 end1begin2 end2){//将较小的数据优先放入tmpif (a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}//当遍历完其中一个区间将另一个区间剩余的数据直接放到tmp的后面while (begin1 end1)tmp[i] a[begin1];while (begin2 end2)tmp[i] a[begin2];//归并完后拷贝回原数组int j 0;for (j left; j right; j)a[j] tmp[j];
}
//归并排序主体函数
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);//申请一个与原数组大小相同的空间if (tmp NULL){printf(malloc fail\n);exit(-1);}_MergeSort(a, 0, n - 1, tmp);//归并排序free(tmp);//释放空间
}
时间复杂度O(N*logN) 空间复杂度O(N)
归并排序非递归实现
归并排序的非递归算法并不需要借助栈来完成我们只需要控制每次参与合并的元素个数即可最终便能使序列变为有序 当然以上例子是一个待排序列长度比较特殊的例子我们若是想写出一个广泛适用的程序必定需要考虑到某些极端情况
情况一 当最后一个小组进行合并时第二个小区间存在但是该区间元素个数不够gap个这时我们需要在合并序列时对第二个小区间的边界进行控制。
情况二 当最后一个小组进行合并时第二个小区间不存在此时便不需要对该小组进行合并。
情况三 当最后一个小组进行合并时第二个小区间不存在并且第一个小区间的元素个数不够gap个此时也不需要对该小组进行合并。可与情况二归为一类
只要把控好这三种特殊情况写出归并排序的非递归算法便轻而易举了。
代码示例
//归并排序子函数
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{int j begin1;//将两段子区间进行归并归并结果放在tmp中int i begin1;while (begin1 end1begin2 end2){//将较小的数据优先放入tmpif (a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}//当遍历完其中一个区间将另一个区间剩余的数据直接放到tmp的后面while (begin1 end1)tmp[i] a[begin1];while (begin2 end2)tmp[i] a[begin2];//归并完后拷贝回原数组for (; j end2; j)a[j] tmp[j];
}
//归并排序主体函数
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);//申请一个与待排序列大小相同的空间用于辅助合并序列if (tmp NULL){printf(malloc fail\n);exit(-1);}int gap 1;//需合并的子序列中元素的个数while (gap n){int i 0;for (i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (begin2 n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个此时不需要对该小组进行合并break;if (end2 n)//最后一组的第二个小区间不够gap个则第二个小区间的后界变为数组的后界end2 n - 1;_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列}gap 2 * gap;//下一趟需合并的子序列中元素的个数翻倍}free(tmp);//释放空间
}
时间复杂度O(N*logN) 空间复杂度O ( N )
