当前位置：首页 > news >正文

【数据结构】排序算法（下篇·终结）·解析数据难点

news 来源：原创 2025/9/17 18:27:19

前引：归并排序作为一种高效排序方法，掌握起来还是有点困难的，何况需要先接受递归的熏陶，这正是编程的浪漫之处，我们不断探索出新的可能，如果给你一串数据让其变得有序？是选择简单的冒泡、插入排序，用暴力美学还是空间换时间？排序算法终结篇——启程！

归并排序（递归）

算法思想：

实现步骤：

复杂度分析：

代码实现：

小静脉：

大动脉：

优缺点分析：

归并排序（非递归）

算法思想：

实现步骤：

分解：

合并：

整体代码：

小编寄语：

归并排序（递归）

咱们又得接受递归的熏陶了！！！归并排序（Merge Sort）是一种基于分治法的高效排序算法，核心思想是将数组分为更小的子数组进行排序，最终合成有序序列，这样看来，我又想到了Hoare大佬的分组方法！此次的分组较于双指针快排递归实现分组究竟有何不同？

算法思想：

（1）分解：将待排序数组递归地分为两个子数组，直到每个子数组仅仅含有一个元素

（2）合并：将两个有序数组合并为一个有序数组，通过比较元素大小依次填入新的数组，再将新数组的内容拷贝回来给原数组

实现步骤：

分解：首先咱们先对这个数组进行递归分组，直到子数组最后只有一个元素结结束递归，每次折半

合并：咱们通过递归已经将子数组分解成了一个元素，现在进行递归返回（合并过程），在合并的过程中对每个数据进行排序，将排序好的元素放入到新数组，每次通过递归返回逐渐扩大子数组，我们每次将合并的数据放在新数组里面（避免覆盖），然后再拷贝回原来的数组

复杂度分析：

咱们每次对半折叠为 logn，分为了左右两组，即每层为n，总的时间复杂度就是O（n logn）

最好最坏都是O（n logn），所以是很稳定的一种排序

我们需要开创一模一样的新数组来作为中间数组，没有额外的空间，因此空间复杂度为O（n）

代码实现：

小静脉：

按照上面的原理，我们需要先开辟一个同样大小的新数组作为辅助。然后有一个问题，如果我们在这个开辟空间里面的函数进行递归，会导致多次开辟空间，因此我们还需要一个子函数，在子函数里面进行递归：

void Merge(int* arr, int size)
{assert(arr);//开辟数组int* tmp = (int*)malloc(sizeof(int) * size);if (tmp == NULL){perror("malloc");return;}//将开辟好的空间地址作为参数传给子函数Sort(arr, tmp ,0 ,size-1);free(tmp)tmp=NULL；
}

大动脉：

这个子函数才是主要的函数，因为里面包括了递归、拷贝等一些列过程，下面我来进行分析：

（1）先对数组进行折半操作

//每次折半
int pivot = (left + right) / 2;

（2）折半之后出现了左右两个数组，分别调用递归进行再次折半，直到满足递归结束条件

//递归结束条件
if (left >= right)
{return;
}
//每次折半
int pivot = (left + right) / 2;
//开始递归
//左区间
Sort(arr, tmp, left, pivot);
//右区间
Sort(arr, tmp, pivot + 1, right);

递归的过程：当左区间满足递归结束条件返回时，会调用右区间的递归函数

此时pivot=0，右区间的区间参数是【1,1】，满足递归结束条件，所以是一层一层进行的

注意：这里的（left+right）千万不能加一，不然当pivot=1时，（1+1）/2=1，就陷入循环了

（3）递归结束之后，开始进行合并。从最后一个递归函数开始，把数据按照有序的形式拷贝给我们的新数组【注：两边的子数组可能长度不一样，需要拷贝子数组元素较多的剩余的元素】。咱们是边拷贝边合并！

递归返回 -> 拷贝给新数组 -> 新数组拷贝给原数组 -> 新一轮

//递归结束进行拷贝
//左区间
int begin1 = left;
int end1 = pivot;
//右区间
int begin2 = pivot + 1;
int end2 = right;
//新数组元素下标
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{//如果左边的子数组开始的元素较大，就先拷贝右边的子数组if (arr[begin1] > arr[begin2]){tmp[i++] = arr[begin2++];}elsetmp[i++] = arr[begin1++];
}
//此时考虑到有剩余的元素
//如果左边子数组有剩余
while (begin1 <= end1)
{tmp[i++] = arr[begin1++];
}
//如果右边的子数组有剩余
while (begin2 <= end2)
{tmp[i++] = arr[begin2++];
}
//现在将新数组的值拷贝回去（注意它的含义是每个递归函数结束了就进行拷贝）
memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));

注意：（1）既然是一层一层进行的，我们需要对左右两个数组区间建立变量

（2）我们拷贝完后，对新数组的元素是没有删除的，因此需要 i++ 同理begin++

（3）拷贝的时候我们的区间不一定是从数组初始位置开始，因此需要加left，同理tmp一样

优缺点分析：

首先时间复杂度稳定在O（n logn），归并为稳定排序，需要额外开辟一个新数组，我们发现只要是小规模的数据都不适合去采用递归、甚至是部分分组排序，它不适用于小规模数据排序

归并排序（非递归）

算法思想：

有了之前的递归基础，咱们已经大概理解了归并的整个过程：先分解再归并

实现步骤：

分解：

当前不用走递归实现了，因此就可以在一个函数中完成分解+合并了，下面正式开始分析：

首先分解：我们之前是通过递归将子数组分为了最后一个元素就进行了合并，然后是两个一组、四个一组、八个一组.......直到最后是整个数组。需要设置一个gap变量，可以理解为当前一个子数组元素的个数，如下图：

下面以gap=1为例进行讲解：

我们先用for循环对两个子数组进行分组，保证每个子数组只有一个元素

int gap = 1;
for (int i = 0; i < size; i += 2*gap)
{//左区间int begin1 = i;int end1 = i + gap - 1;//右区间int begin2 = i + gap;int end2 = i + 2 * gap - 1;
}

例如左区间元素下标：【0,0】【2,2】【4,4】........

对应右区间元素下标：【1,1】【3,3】【5,5】........

这个规律是怎么找的呢？左区间、右区间每次变化2，如下图参考：

合并：

上面我们已经对子数组以一个元素为列进行了分组，下面进行合并，只需要拷贝递归代码即可：

int j = i;
while (begin1 <= end1 && begin2 <= end2)
{//如果左边的子数组开始的元素较大，就先拷贝右边的子数组if (arr[begin1] > arr[begin2]){tmp[j++] = arr[begin2++];}elsetmp[j++] = arr[begin1++];
}
//此时考虑到有剩余的元素
//如果左边子数组有剩余
while (begin1 <= end1)
{tmp[j++] = arr[begin1++];
}
//如果右边的子数组有剩余
while (begin2 <= end2)
{tmp[j++] = arr[begin2++];
}
//现在将新数组的值拷贝回去
memcpy(arr + i, tmp + i, sizeof(int) * （end2-i+1）);

注意拷贝个数应该是左右两个子数组元素之和，也就是2倍的gap，通过下面调试看到没有问题：

下面我们再通过再套一个循环，改变gap，就完成了所有的分组，但是出现了一个新问题。

我们通过打印每次的区间，可以看到有越界的情况，因为gap后面越来越大，而2倍的gap就存在越界，如下图：

所以咱们针对这个越界的情况（同时避免了元素个数是偶数、奇数的问题）需要进行分类讨论：

（1）如果end1越界，那么后面的【begin2，end2】肯定越界了

（2）如果end1、begin2没有越界，那end2肯定越界了

（3）如果end1刚好在元素末尾，begin2越界了

//修正
if (end1 >= size)
{end1 = size - 1;//begin2、end2写一个不符合条件的区间begin2 = size;end2 = size - 1;
}
if (begin2 >= size)
{begin2 = size;end2 = size - 1;
}
if (end2 >= size)
{end2 = size - 1;
}

以上就是所有的情况了！为什么只判断只有一个区间中的一个界限出界的情况？

因为我们下面的循环会判断一整个单个区间的情况，但是无法判断两个区间交并的情况。

更改措施：我们利用下面的循环条件，只要出界时是一个不合法的区间，那么就无法进入循环了

整体代码：

我们观察修改前后区间的变化，以及排序效果：

//归并排序·非递归
void MergeSort(int* arr, int size)
{assert(arr);//开辟数组int* tmp = (int*)malloc(sizeof(int) * size);if (tmp == NULL){perror("malloc");return;}//分解int gap = 1;while (gap < size){for (int i = 0; i < size; i += 2 * gap){//左区间int begin1 = i;int end1 = i + gap - 1;//右区间int begin2 = i + gap;int end2 = i + 2 * gap - 1;printf("修改前：[%d,%d] [%d,%d]\n", begin1, end1, begin2, end2);//修正if (end1 >= size){end1 = size - 1;//begin2、end2写一个不符合条件的区间begin2 = size;end2 = size - 1;}if (begin2 >= size){begin2 = size;end2 = size - 1;}if (end2 >= size){end2 = size - 1;}printf("修改后：[%d,%d] [%d,%d]\n", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){//如果左边的子数组开始的元素较大，就先拷贝右边的子数组if (arr[begin1] > arr[begin2]){tmp[j++] = arr[begin2++];}elsetmp[j++] = arr[begin1++];}//此时考虑到有剩余的元素//如果左边子数组有剩余while (begin1 <= end1){tmp[j++] = arr[begin1++];}//如果右边的子数组有剩余while (begin2 <= end2){tmp[j++] = arr[begin2++];}//现在将新数组的值拷贝回去memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));}printf("\n");gap *= 2;}free(tmp);tmp = NULL;
}

小编寄语

这篇文章结束就代表在数据初阶排序算法就收尾了，我们一起经历了这么多，现在我们一起去探索新的可能吧！接下来小编会持续更新数据结构算法题目哦！接下来不妨一键三连，跟小编一起刷题！

归并排序（递归）

算法思想：

实现步骤：

复杂度分析：

代码实现：

小静脉：

大动脉：

优缺点分析：

归并排序（非递归）

算法思想：

实现步骤：

分解：

合并：

整体代码：

小编寄语

相关文章：