本文讲解的排序算法是归并排序,作为归并算法,其有着快速排序算法没有的特性,也是面试比较常考的算法之一。本文会重点讲解思路以及代码的实现。
OK,让我们来一场酣畅淋漓的排序冒险吧!!!
归并排序(MergeSort)是一种基于分治法的高效排序算法,具有稳定性和较好的时间复杂度。归并排序的基本思想是将待排序数组递归地分成两个子数组,分别对这两个子数组进行排序,然后再将它们合并成一个有序数组。
我给大家看一下归并排序的动图:
也许你看到上面的步骤有点云里雾里的感觉,没有关系,下面我将给出一个具体的例子,带着大家,去理解上面的步骤。
🍇例子:假设我们要对数组 [3, 1, 4, 1, 5, 9, 2, 6] 进行归并排序:
相信来看完上面的例子,你已经了解了归并排序的玩法了,那么接下来我们就得用代码来实现了。
大家可以对照着这幅图来理解:
可以看到归并排序的思想一定可以用递归来思想,接下来,我先给大家完整的代码,之后会对代码的关键部分讲解:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
if(a[begin1] >= a[begin2])
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + left, tmp + left, sizeof(int)*(right-left+1));
}
//归并排序
void MergeSort(int* a, int n)
{
int left = 0, right = n - 1;
int* tmp = (int*)malloc(n * sizeof(int));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a,left,right,tmp);
}
这里我们采用的是用_MergeSort这个函数写归并排序的核心代码,这种写法的结构也是现在比较推崇的。
为了让大家更好的吸收上述代码的思想,这里我将会详细的讲解代码关键部分的逻辑。
我们直到归并排序是采用分治思想的,其原理就是将一个数组拆解成一个一个有序的区间,最后经过比较合并之后才会称为一个有序的数组。那么,我们该如何,将数组拆成一个个区间呢?
利用递归就可以实现。有的人可能会问了,为什么会使用递归呢?
你可以这样想:我每次以数组中间位置的元素为界限,将数组拆分成两半。紧接着,又对已经拆分成两半的那两个数组再次进行这个操作。直至拆到没有元素或者是只剩一个元素为止,所以我们就可以推导出递归的条件为:左区间是否大于等于右区间。
这段代码的作用:将拆解的数组的元素放到一个临时空间中进行重新排序。
有的人会问,那最后两个循环是怎么回事?
其实是这样的,你可以假设现在你有两个有序的数组,你要将这两个数组组成一个有序(升序)的数组,你会这么做:首先,你会分别拿出两个数组中的第一个元素互相比较,发现有其中一个元素的值比另一个要小,你就把那个小的元素的值放到一个你为一个有序(升序)的数组而申请的内存空间中,之后就拿下一个元素跟这个上次那个元素的值进行比较。 到后面,你会发现肯定有个数组里面的元素是没有被选中的,但是我们也不知道是哪一个,所以我们就可以都遍历一遍找到还没有被选中的元素,将它加进到你申请的空间中。
这里你可以使用for循环,也可以用一个函数memcpy。这里我选择用后者。
当然,里面的参数十分的讲究。
解释:
非递归归并排序的主要步骤:
非递归归并排序的核心思想:归并排序的递归版从上到下拆分数组,而非递归版则从下到上逐步合并,模拟递归中“合并”的过程。在这个过程中,我们通过循环控制子数组的长度,每次将相邻的子数组合并成更大的有序数组。
具体步骤:
由此,我们就可以通过上述思想,写出两个版本的代码: 版本1:
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap <= n / 2)
{
for (int i = 0; i < n; i += 2 * gap)
{
//划分区间:[begin1,end1][begin2,end2]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//控制区间的边界
if (end1 >= n)
{
end1 = n - 1;
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
}
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));
}
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
free(tmp);
tmp = NULL;
}
版本2:
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap <= n / 2)
{
for (int i = 0; i < n; i += 2 * gap)
{
//划分区间:[begin1,end1][begin2,end2]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
好了,到这里归并排序的内容就已经全部讲完了。如果大家觉得本文写的还不错的话。麻烦给偶点个赞吧!!!