归并排序递归写法
一. 基本概念
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
说了那么一大堆的话 其实中心思想就两个字 分治
二. 图解
我们要将整个数组有序就是要将它的左右数组都变得有序
我们要想将左右数组都变得有序就是要将它左数组的左右数组和右数组的左右数组变得有序
依次套娃
到最后面呢
会变成一个个单个的元素 这个时候肯定是有序了嘛
当它变成有序之后我们再一个一个的归
我们来看代码
// 创建一个临时的数组 int* tmp = (int*)malloc(sizeof(int) * (right + 1)); if (tmp==NULL) { printf("mergesort malloc error"); exit(-1); }
这里我们首先要创建一个临时的数组来归并存贮数据 不然的话再内部排序会打乱顺序
之后我们开始考虑递归的问题
void _mergesort(int* arr, int left, int right,int* tmp) { // assert assert(arr); // 限制条件 if (left>=right) { return; } // 开始递归 int mid = (left + right) / 2; _mergesort(arr, left, mid,tmp); _mergesort(arr, mid+1, right,tmp);
我们先来看这一段
这里开始递归如果没有达到边界条件的话 （只有一个元素）
就往左和右继续走
递完毕了之后我们开始归
这里注意看图
// 开始归 int end1 = left; int end2 = mid + 1; int i = left; // 开始将两个子数组中的内容 归并到tmp数组中 while (end1<=mid && end2<=right) { if (arr[end1]<arr[end2]) { tmp[i++] = arr[end1++]; } else { tmp[i++] = arr[end2++]; } } while (end1<=mid) { tmp[i++] = arr[end1++]; } while (end2<=right) { tmp[i++] = arr[end2++]; } // tmp数组里面被放满了 排序好的值 // tmp里面的值 全部赋值到arr里面了 for ( i = 0; i < right+1; i++) { arr[i] = tmp[i]; } }
再之后我们将临时数组里面的值一一放到arr里面就好啦
这里有一点要注意的是i的赋值
这里的i要赋值left才可以
因为我们我们每次归的范围不同
当时这里写过了debug了很久
归并排序的非递归写法
我们首先来看下递归的思路
这边是分解成单个的元素然后让它们进行归并
单个元素进行好之后归并之后就继续两个元素进行归并
两个元素进行好归并之后就继续四个元素进行归并
四个元素进行好归并之后就继续八个元素进行归并
我们的非递归思路的主要思想就是用循环进行分割数组
如图
首先分割成八个
再之后分割成四个
再之后分割成两个
如果最后成为一个了之后
它就直接变成有序的了
我们这里的代码如下（其实就是照抄归那一段代码 修改了一小部分 ）
我们这里使用gap来进行分割
这是一个很巧妙的思路
当gap等于1的时候 数组就只有一个元素
当gap等于2的时候 数组就有两个元素
// 将两个数组中的代码归并到 一个临时数组中 for (int i = 0; i < size; i += 2*gap) { int bejin1 = i; int end1 = i + gap - 1; int bejin2 = i + gap; int end2 = i + 2*gap - 1; int index = i; while (bejin1 <= end1 && bejin2 <= end2) { if (arr[bejin1]<arr[bejin2]) { tmp[index++] = arr[bejin1++]; } else { tmp[index++] = arr[bejin2++]; } } while (bejin1<=end1) { tmp[index++] = arr[bejin1++]; } while (bejin2<=end2) { tmp[index++] = arr[bejin2++]; } } // 拷贝回原数组中 for (int i = 0; i < size; i++) { arr[i] = tmp[i]; } gap *= 2; }
当然最后我们需要将整个排序好的数组拷贝到原数组中
不然的话 的话其实就只是排序了最后一次 ！！
改bug
当然这里的代码肯定是不正确的
当我们的数组个数不是2的n次方的时候 这里的程序就会出现bug
如图
这里 是不是很明显的会造成一个数组越界的情况啊
我们仔细分析下
对于我们的三个边界
begin1肯定是不可能越界的
begin2 end1 end2都有可能越界
那这个时候怎么办呢？
我们就要根据这三种情况一一给出解决思路
当end1越界的时候我们是不是只要修正下边界就可以了
再将第二个数组置为不存在
当begin2越界的时候也是一个思路 置为不存在
当end2越界的时候呢 跟end1越界的思路一样 这里我们修正下边界就好
修正代码如下
// 第一种越界情况 if (end1 > size-1) { end1 = size - 1; // 设置第二个数组不存在 bejin2 = size; end2 = size - 1; } // 第二种越界情况 if (bejin1>size-1) { // 设置第二个数组不存在 bejin2 = size; end2 = size - 1; } // 第三种越界情况 if (end2 > size-1) { end2 = size - 1; }
完整代码如下
void _mergesortnonR(int* arr, int size) { // assert assert(arr); int gap = 1; // 创建一个临时的数组 int* tmp = (int*)malloc(sizeof(int) * (size)); if (tmp == NULL) { printf("mergesort malloc error"); exit(-1); } while (gap < size) { // 将两个数组中的代码归并到 一个临时数组中 for (int i = 0; i < size; i += 2*gap) { int bejin1 = i; int end1 = i + gap - 1; int bejin2 = i + gap; int end2 = i + 2*gap - 1; // 第一种越界情况 if (end1 > size-1) { end1 = size - 1; // 设置第二个数组不存在 bejin2 = size; end2 = size - 1; } // 第二种越界情况 if (bejin1>size-1) { // 设置第二个数组不存在 bejin2 = size; end2 = size - 1; } // 第三种越界情况 if (end2 > size-1) { end2 = size - 1; } int index = i; while (bejin1 <= end1 && bejin2 <= end2) { if (arr[bejin1]<arr[bejin2]) { tmp[index++] = arr[bejin1++]; } else { tmp[index++] = arr[bejin2++]; } } while (bejin1<=end1) { tmp[index++] = arr[bejin1++]; } while (bejin2<=end2) { tmp[index++] = arr[bejin2++]; } } // 拷贝回原数组中 for (int i = 0; i < size; i++) { arr[i] = tmp[i]; } gap *= 2; } free(tmp); tmp = NULL; }
几个注意点
这里我们需要注意的点有三点
1. 注意排序完一次之后需要将临时数组里的内容拷贝回去
2. 注意begin1 begin2 end1 end2的边界 这个还是蛮难想的
3. 注意数组越界问题 对于三种可能越界情况要给予修正
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
