好的,我来按照你提供的目录来讲解归并排序的基本思想和实现。
归并排序是一种典型的分治算法。 基本思想是:
这个过程可以递归地进行,直到整个数组有序为止。
归并排序的时间复杂度为 O(n log n)
,是一种非常高效的排序算法。
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//tmp数组初始化
memset(tmp, '0', sizeof(int) * n);
// 调用递归函数进行排序
_MergeSort(a, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}
在MergeSort()
函数中,我们首先申请一个临时数组tmp
,用于存储排序后的结果,然后我们调用_MergeSort()
函数进行排序。_MergeSort()
函数会递归地将数组分成两个子数组,并对这两个子数组进行排序和合并,最后,我们释放临时数组tmp
// 如果区间只有一个元素,则直接返回
if (begin == end)
return;
[begin, end]
分成两个子区间[begin, mid]
和[mid+1, end]
,分别对这两个子区间进行递归排序。 // 将区间分成两个子区间
int mid = (begin + end) / 2;
// [begin, mid] [mid+1, end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
begin1
和begin2
,分别指向两个子区间的起始位置。然后我们比较这两个指针指向的元素,将较小的元素插入到临时数组tmp
中。当一个子区间中的元素全部被插入到tmp
中后,我们将剩余的元素直接插入到tmp
中。 // 归并操作
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
// 依次比较两个子区间的元素,取小的尾插tmp数组
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
// 将剩余的元素插入tmp数组
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
tmp
拷贝回原数组a
中。 // 将排序好的区间拷贝回原数组
memcpy(a+begin, tmp + begin, sizeof(int) * (end - begin + 1));
完整的代码:
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
// 调用递归函数进行排序
_MergeSort(a, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
// 如果区间只有一个元素,则直接返回
if (begin == end)
return;
// 将区间分成两个子区间
int mid = (begin + end) / 2;
// [begin, mid] [mid+1, end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
// 归并操作
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
// 依次比较两个子区间的元素,取小的尾插tmp数组
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
// 将剩余的元素插入tmp数组
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
// 将排序好的区间拷贝回原数组
memcpy(a+begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
非递归版本的归并排序的思想和递归版本是一致的,都是采用分治的思想。不同之处在于,递归版本使用递归调用来实现分治,而非递归版本使用循环来实现,有点类似于斐波那契数列,由前面两个相加推出后面。
非递归实现步骤如下:
tmp
:int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//tmp数组初始化
memset(tmp, '0', sizeof(int) * n);
这段代码申请了一个大小为 n
的临时数组 tmp
。如果内存申请失败,则打印错误信息并返回。
gap
变量:int gap = 1;
gap
变量用于控制每次合并的区间大小。初始时 gap
为 1,表示每次合并相邻的两个元素。
while (gap < n)
{
// ...
gap *= 2;
}
这个 while
循环不断增大 gap
的值,直到 gap
大于等于数组的长度 n
。在每次循环中,我们将 gap
乘以 2,这样可以保证每次合并的区间大小都是上一次的 2 倍。
for (int j = 0; j < n; j += 2 * gap)
{
int begin1 = j, end1 = begin1 + gap - 1;
int begin2 = begin1 + gap, end2 = begin2 + gap - 1;
// 越界的问题处理
if (end1 >= n || begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
int i = j;
// 依次比较,取小的尾插tmp数组
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + j, tmp + j, sizeof(int) * (end2-j+1));
}
这段代码是内部循环,它遍历数组,每次处理两个区间 [begin1, end1]
和 [begin2, end2]
。
首先,我们需要处理可能出现的越界情况。如果 end1
大于等于 n
,或者 begin2
大于等于 n
,则表示第二个区间已经超出了数组的范围,我们直接 break
。如果 end2
大于等于 n
,则将其设置为 n-1
。
然后,我们比较这两个区间的元素,将较小的元素依次插入到 tmp
数组中。当一个区间中的元素全部被插入到 tmp
中后,我们将剩余的元素直接插入到 tmp
中。
最后,我们将排序好的区间从 tmp
拷贝回原数组 a
中。
free(tmp);
tmp = NULL;
在循环结束后,我们释放临时数组 tmp
。
非递归版本的归并排序算法的时间复杂度也是 O(nlogn)
,空间复杂度为 O(n)
。
处理数组越界的问题。 为什么还要处理越界问题 当数组的数组数据不够合并时,而且越界合并一些不属于的空间,因此:会导致归并越界问题:
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
if (end1 >= n || begin2 >= n)
这个条件是检查是否已经超出了数组的范围,如果 end1
大于等于数组长度 n
,或者 begin2
大于等于数组长度 n
,说明第二个区间已经超出了数组的范围,这种情况下我们直接 break
跳出当前循环。
if (end2 >= n)
这个条件是检查第二个区间的结束下标 end2
是否超出了数组的范围。如果 end2
大于等于数组长度 n
,说明第二个区间的结束下标超出了数组的范围,此时我们将 end2
设置为 n-1
。这样可以确保第二个区间的结束下标不会超出数组的范围,从而避免了数组越界的问题。
完整代码:
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//tmp数组初始化
memset(tmp, '0', sizeof(int) * n);
int gap = 1;
while (gap < n)
{
//printf("gap:%d->", gap);
for (int j = 0; j < n; j += 2 * gap)
{
int begin1 = j, end1 = begin1 + gap - 1;
int begin2 = begin1 + gap, end2 = begin2 + gap - 1;
//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
// 越界的问题处理
if (end1 >= n || begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
int i = j;
// 依次比较,取小的尾插tmp数组
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + j, tmp + j, sizeof(int) * (end2-j+1));
}
//printf("\n");
gap *= 2;
}
free(tmp);
tmp = NULL;
}
void TestMergeSort()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
PrintArray(a, sizeof(a) / sizeof(int));
MergeSortNonR(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
归并排序的特性总结:
O(N)
的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。O(N*logN)
O(N)