排序——归并排序及排序章节总结

前面的文章中 我们详细介绍了排序的概念，插入排序，交换排序与选择排序，大家可以通过下面的链接再去学习：

​​​​​​排序的概念及插入排序

交换排序

选择排序

这篇文章就详细介绍一下另一种排序算法：归并排序以及对排序章节进行一下总结。

一，归并排序基本概念

归并：将两个或两个以上的有序表组合成一个新有序表

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）分布随机，则采用简单选择排序，若排序码不接近逆序，也可以采用直接插入排序。

到此排序就结束了， 如果文章对你有用的话请点个赞支持一下吧！