前面的文章中 我们详细介绍了排序的概念,插入排序,交换排序与选择排序,大家可以通过下面的链接再去学习:
排序的概念及插入排序
交换排序
选择排序
这篇文章就详细介绍一下另一种排序算法:归并排序以及对排序章节进行一下总结。
一,归并排序基本概念
归并:将两个或两个以上的有序表组合成一个新有序表
2-路归并排序
排序过程
初始序列看成n个有序子序列,每个子序列长度为1
两两合并,得到 ë n/2 û 个长度为2或1的有序子序列
例:
将两个顺序表合成一个有序表
两个有序子序列的归并
设两个有序表存放在同一数组中相邻的位置上:R[low..mid]和R[mid + 1..high]
每次分别从两个表中取出一个记录进行关键字的比较,将较小者放入T[1ow..high]中
在代码中实现:
void Merge(RedType R[],RedType &T[],int low,int mid,int high)
{ i=low;j=mid+1;k=low; while(i<=mid&&j<=high) //将R中记录由小到大地并入T中{ if(R[i].key<=R[j].key) T[k]=R[i++]; else T[k]=R[j++]; } while(i<=mid) T[k++]=R[i++]; //将剩余的R[low..mid]复制到T中 while(j<=high) T[k++]=R[j++];//将剩余的R[j.high]复制到T中
}
归并排序的递归
2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时,递归结束,否则:
① 将当前序列一分为二,求出分裂点mid = (low+high)/2;
② 对子序列R[low..mid]递归,结果放入S[low..mid]中;
③ 对子序列R[mid + 1..high]递归,结果放入S[mid + 1..high]中;
具体的代码实现递归过程:
void MSort(RedType R[],RedType &T[],int low,int high)
{ if(low==high) T[low]=R[low]; else{ mid=(low+high)/2; //将当前序列一分为二,求出分裂点mid MSort(R,S,low,mid); //R[low..mid]递归,结果放入S[low..mid] MSort(R,S,mid+1,high);//R[mid+1..high]递归,结果放入S[mid+1..high]Merge(S,T,low,mid,high);//将S[low..mid]和S[mid+1..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)
空间效率:O(n)
稳 定 性:稳定
二,排序章节总结
各种排序算法的性能:
首先通过下面这个图表对比一下
(数据不是顺次后移时将导致方法不稳定)
按平均时间排序方法分为四类
O(n2)、O(nlogn)、O(n1+e )、O(n)
•快速排序是基于比较的内部排序中平均性能最好的
• 基数排序时间复杂度最低,但对关键字结构有要求
知道各级关键字的主次关系
知道各级关键字的取值范围
为避免顺序存储时大量移动记录的时间开销,可考虑用链表作为存储结构:直接插入排序、归并排序、基数排序 。
不宜采用链表作为存储结构的折半插入排序、希尔排序、快速排序、堆排序 。
排序算法的选择规则:
当n较大时
(1)分布随机,稳定性不做要求,则采用快速排序
(2)内存允许,要求排序稳定时,则采用归并排序
(3)可能会出现正序或逆序,稳定性不做要求,则采用堆排序或归并排序
当n较小时
(1)基本有序,则采用直接插入排序
(2)分布随机,则采用简单选择排序,若排序码不接近逆序,也可以采用直接插入排序。
到此排序就结束了, 如果文章对你有用的话请点个赞支持一下吧!