【排序算法】归并排序

学习起来吧

发布于 2024-05-11 08:11:30

600

发布于 2024-05-11 08:11:30

文章被收录于专栏：学习C/++学习C/++

📝 归并排序

🌠 归并排序

好的,我来按照你提供的目录来讲解归并排序的基本思想和实现。

归并排序是一种典型的分治算法。基本思想是:

将待排序的数组划分成两个子数组(左右两部分)。
递归地对左右两个子数组进行排序。
将排好序的左右子数组合并成一个有序数组。

这个过程可以递归地进行,直到整个数组有序为止。

归并排序的时间复杂度为 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));
}