排序算法-----归并排序

目录

前言：

归并排序

1. 定义

2.算法过程讲解

2.1大致思路

2.2图解示例

拆分合成步骤

 ​编辑

相关动态图 

 3.代码实现（C语言）

4.算法分析

4.1时间复杂度

4.2空间复杂度

 4.3稳定性

---

前言：

        今天我们就开始学习新的排序算法----归并排序，说到归并排序，最重要的思想就是分而治之，先分后治。相较于前面所学过的排序算法，归并排序过程相对比较复杂，但是不要慌！我会详细讲解这个过程的！下面我们就一起来学习吧！

归并排序

1. 定义

        归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

2.算法过程讲解

2.1大致思路

已知一个数组arr[0,n-1],实现对这个数组进行拆分为arr[0,n/2]和arr[n/2+1,n-1]然后对这个数组进行进一步对半拆分，直到拆成每个分数组里面只有一个元素时，结束拆分；然后进入排序，按照拆分过程的路径进行排序合并，直到合并为一个数组的时候结束，最终得到的数组就是排序完成的数组。

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果

2.2图解示例

拆分合成步骤

已知一个数组  [6,5,3,1,8,7,2,4]，要求通过归并排序进行排序

第一步，依次拆分，直到每一个分数组剩下一个元素 ，如下所示：

                                                 6 5 3 1 8 7 2 4

第一次拆分                  6 5 3 1                           8 7 2 4

第二次拆分            6 5            3 1                8 7             2 4

第三次拆分        6        5       3        1        8        7       2        4

第二步，拆分完成之后，就进行排序        合并,如下所示：

                            6        5       3        1        8        7       2        4

第一次合并：          5 6               1 3              7 8              2 4      

第二次合并：                 1 3 5 6                            2 4 7 8

第三次合并：                              1 2 3 4 5 6 7 8

 以上步骤就完成了归并排序的过程了，演示图如下所示：

 动态图：

 

相关动态图 

 3.代码实现（C语言）

#include<stdio.h>
//归并排序
//合成排序
void merge(int* n,int *temp,int left,int mid,int rigth) {int l_pos = left;int r_pos = mid+1;int pos = left;//左右两部分数组进行比较合并while (l_pos <= mid && r_pos <= rigth) {if (n[l_pos] < n[r_pos])temp[pos++] = n[l_pos++];elsetemp[pos++] = n[r_pos++];}//如果左边还有多余的就直接补到后面去while (l_pos <= mid)temp[pos++] = n[l_pos++];//如果右边有多余的就直接补到后面去while (r_pos <= rigth)temp[pos++] = n[r_pos++];//这里只需要把原来的数组覆盖掉就行了while (left <= rigth) {n[left] = temp[left];left++;}}
//拆分与归并
void msort(int *n,int *temp,int left,int right) {if (left < right) {			int mid = (left + right) / 2;	//先拆分为两部分msort(n, temp, left, mid); //左边递归msort(n, temp, mid+1, right);//右半递归merge(n, temp, left, mid, right);	//拆分完成之后进行归并和排序}
}
//排序函数接口
void merge_sort(int* n, int length) {int* temp = (int*)malloc(sizeof(int) * length);//申请一个同样大小的辅助数组空间if (temp) {//如果申请成功msort(n, temp, 0, length-1);    //进入到排序free(temp);						//释放掉这个空间}else {printf("Space allocation failure");}
}int main() {int array[8] = { 25,24,6,65,11,43,22,51 };printf("排序前:");for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}printf("\n排序后：");merge_sort(array, sizeof(array) / sizeof(int));for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}
}
//排序前:25 24 6 65 11 43 22 51
//排序后：6 11 22 24 25 43 51 65

4.算法分析

4.1时间复杂度

        归并排序的速度仅次于快速排序，速度是相当快的。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序时间复杂度为O(nlogn)。

4.2空间复杂度

 你知道么，归并排序在任何情况下的时间复杂度永远都是 O(nlogn)，是不是很奇怪呢？别急，凡事有得必有失，归并排序是通过牺牲空间的代价来实现减小时间复杂度的。上面的代码涉及到数据暂存空间的开辟，其开辟的空间数量最大也不会超过n，所以空间复杂度为O(n)

 4.3稳定性

归并排序是稳定的排序算法，因为无论是在排序拆解过程中还是在归并过程中都没有改变相同元素的相对位置，所以是稳定的。

 好了，以上就是今天的全部内容了，你们学会了吗?我们下一期再见！