怎么给网站做spm,特产网站建设,网站跟app区别,营销策划方案模板范文前面的文章中 我们详细介绍了排序的概念#xff0c;插入排序#xff0c;交换排序与选择排序#xff0c;大家可以通过下面的链接再去学习#xff1a;
排序的概念及插入排序
交换排序
选择排序
这篇文章就详细介绍一下另一种排序算法#xff1a;归并排序以及…前面的文章中 我们详细介绍了排序的概念插入排序交换排序与选择排序大家可以通过下面的链接再去学习
排序的概念及插入排序
交换排序
选择排序
这篇文章就详细介绍一下另一种排序算法归并排序以及对排序章节进行一下总结。
一归并排序基本概念
归并将两个或两个以上的有序表组合成一个新有序表
2-路归并排序
排序过程
初始序列看成n个有序子序列每个子序列长度为1
两两合并得到 ë n/2 û 个长度为2或1的有序子序列 再两两合并重复直至得到 一个 长度为 n 的有序序列为止 例
将两个顺序表合成一个有序表 两个有序子序列的归并
设两个有序表存放在同一数组中相邻的位置上R[low..mid]和R[mid 1..high]
每次分别从两个表中取出一个记录进行关键字的比较将较小者放入T[1ow..high]中 重复 此过程直至其中一个表为空最后将另一非空表中余下的部分直接复制到 T 中 在代码中实现
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{ ilow;jmid1;klow; while(imidjhigh) //将R中记录由小到大地并入T中{ if(R[i].keyR[j].key) T[k]R[i]; else T[k]R[j]; } while(imid) T[k]R[i]; //将剩余的R[low..mid]复制到T中 while(jhigh) T[k]R[j];//将剩余的R[j.high]复制到T中
}归并排序的递归
2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时递归结束否则
① 将当前序列一分为二求出分裂点mid (lowhigh)/2
② 对子序列R[low..mid]递归结果放入S[low..mid]中
③ 对子序列R[mid 1..high]递归结果放入S[mid 1..high]中 ④ 调用算法 Merge 将 S[ low..mid ] 和 S[mid 1..high] 归并 T[ low..high ] 。 具体的代码实现递归过程
void MSort(RedType R[],RedType T[],int low,int high)
{ if(lowhigh) T[low]R[low]; else{ mid(lowhigh)/2; //将当前序列一分为二求出分裂点mid MSort(R,S,low,mid); //R[low..mid]递归结果放入S[low..mid] MSort(R,S,mid1,high);//R[mid1..high]递归结果放入S[mid1..high]Merge(S,T,low,mid,high);//将S[low..mid]和S[mid1..high]归并到T[low..high]}
} 下面是一段完整的归并排序实例
#include stdio.h// 合并两个子数组的函数
void merge(int arr[], int l, int m, int r) {int i, j, k;int n1 m - l 1; // 左子数组的大小int n2 r - m; // 右子数组的大小int L[n1], R[n2]; // 创建临时数组// 复制数据到临时数组 L[] 和 R[]for (i 0; i n1; i)L[i] arr[l i];for (j 0; j n2; j)R[j] arr[m 1 j];// 合并临时数组回 arr[l..r]i 0; // 初始化第一个子数组的索引j 0; // 初始化第二个子数组的索引k l; // 初始化合并后的子数组的索引while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}// 复制 L[] 的剩余元素如果有的话while (i n1) {arr[k] L[i];i;k;}// 复制 R[] 的剩余元素如果有的话while (j n2) {arr[k] R[j];j;k;}
}// 归并排序的主函数
void mergeSort(int arr[], int l, int r) {if (l r) {int m l (r - l) / 2; // 计算中间点mergeSort(arr, l, m); // 递归排序左半部分mergeSort(arr, m 1, r); // 递归排序右半部分merge(arr, l, m, r); // 合并左右两部分}
}int main() {int arr[] {12, 11, 13, 5, 6, 7};int arr_size sizeof(arr) / sizeof(arr[0]);printf(给定的数组是 );for (int i 0; i arr_size; i)printf(%d , arr[i]);printf(\n);mergeSort(arr, 0, arr_size - 1); // 对整个数组进行归并排序printf(排序后的数组是 );for (int i 0; i arr_size; i)printf(%d , arr[i]);return 0;
}算法分析
时间效率O(nlog2n) 空间效率On
稳 定 性稳定 二排序章节总结 各种排序算法的性能 首先通过下面这个图表对比一下 数据不是顺次后移时将导致方法不稳定 按平均时间排序方法分为四类 O(n2)、O(nlogn)、O(n1e )、O(n) •快速排序是基于比较的内部排序中平均性能最好的 • 基数排序时间复杂度最低但对关键字结构有要求 知道各级关键字的主次关系 知道各级关键字的取值范围
为避免顺序存储时大量移动记录的时间开销可考虑用链表作为存储结构直接插入排序、归并排序、基数排序 。
不宜采用链表作为存储结构的折半插入排序、希尔排序、快速排序、堆排序 。 排序算法的选择规则
当n较大时
1分布随机稳定性不做要求则采用快速排序
2内存允许要求排序稳定时则采用归并排序
3可能会出现正序或逆序稳定性不做要求则采用堆排序或归并排序
当n较小时
1基本有序则采用直接插入排序
2分布随机则采用简单选择排序若排序码不接近逆序也可以采用直接插入排序。 到此排序就结束了 如果文章对你有用的话请点个赞支持一下吧
