数据结构排序算法详解（4）——归并排序（附动图)

用户11983512

发布于 2026-01-09 14:53:48

1390

文章被收录于专栏：用户11983512的专栏用户11983512的专栏

前言

嗨٩(๑>◡<๑)۶ ，我们又见面啦，上一篇我们讲解了交换排序，见到了交换排序的魅力，今天我们来了解排序的最后一类——归并排序，让我们一起去了解吧！

七、归并排序

1、归并排序的思想（含动图）

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：

和我们之前写的把两个有序数组和并为一个有序数组一样，但数组无序怎么办呢？ 那我们就把他分成一个一个元素——分解阶段 再创建一个新的数组，通过比较合并到新的数组中（防止覆盖原数组），最后再转移到原数组中——合并过程 可以结合下面这个动图来理解（不含分解过程（默认分解完成））

2、递归实现归并排序

这里使用取中间元素进行分解数组

（1）代码

利用上面的思路进行实现代码如下：

// 时间复杂度：O(N * logN)
// 空间复杂度：O(N)
// 递归实现归并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{
    if (begin >= end)
        return;

    int mid = (begin + end) / 2;
    // 如果[begin, mid][mid+1, end]有序就可以进行归并了
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);//分解过程

    // 归并
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin;
    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 + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    _MergeSort(a, tmp, 0, n - 1);

    free(tmp);
    tmp = NULL;
}

测试递归

int main()
{
    int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
	MergeSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
    //TestOP();
    return 0;
}

结果均正确

（2）主要内容分析

这里递归主函数只用传数组地址和元素个数就行啦，他会自己进行计算左右

这个函数是进行递归，取中间原素进行拆解

这里只能把它分解为【begin,mid】和【mid+1，end】这两个区间为什么呢？当我们把它换成【begin,mid-1】和【mid，end】 比如我们现在区间为【2,3】->[2,1][2,3]我们可以发现左区间错误，右区间不变导致死循环，所以我们采用【begin,mid】和【mid+1，end】

3、归并的非递归版本

（1）思路

非递归版本的归并排序（迭代实现），核心思想是 “自底向上合并”子数组，无需递归，直接通过循环控制分组大小（gap），逐步完成排序。

相当于就是直接从最小的有序单元（长度为 1 的子数组）开始，主动将相邻的有序子数组两两合并，逐步扩大有序子数组的长度，最终是原数组变的有序

（2）关键枢纽——gap的迭代与分组逻辑

非递归归并的核心控制变量是gap，它代表当前待合并的有序子数组长度：

初始gap=1：此时每个元素都是长度为1的有序子数组（单个元素天然有序）；
每轮合并完成后，gap会乘以2（即gap *= 2）：有序子数组的长度随之倍增（1→2→4→8…）；
当gap超过数组长度时，整个数组已合并为一个有序单元，排序完成。

gap的倍增是驱动排序推进的关键：每一次倍增，有序子数组的规模扩大一倍，直到覆盖整个数组。同时，gap的作用是定义子组长度、划分待合并子组——每轮循环中，数组会被划分为若干个长度为gap的子组，每两个相邻子组构成一组“待合并对象”。相当于比如刚开始gap=1，就是两个元素个数为1的数组合并，gap=2，就是两个元素个数为2的数组合并……直到所有数组合并为一个数组，就是有序的具体思路如下图：

这里几几归并就是，元素个数为几的两个数组合并

（3）具体过：分组→合并→覆盖的闭环

非递归归并的每一轮循环遵循“分组→合并→覆盖”逻辑，gap的倍增贯穿全程：

分组：按gap划分相邻子组 以gap=1为例，数组[10,6,7,1,3,9,4,2]被划分为[10]&[6]、[7]&[1]等四对相邻子组；gap *= 2变为2时，子组长度扩为2，划分结果为[6,10]&[1,7]等；gap再倍增为4时，子组长度为4，划分结果为[1,6,7,10]&[2,3,4,9]。
合并：双指针归并有序子组 对每对相邻子组，用双指针（分别指向子组起始）遍历，将较小元素存入临时数组（避免原数组数据覆盖）。例：合并[10]&[6]时，指针1指向10、指针2指向6，先存6再存10，得到有序子组[6,10]。
覆盖：将结果写回原数组 每对相邻子组合并后，把临时数组中对应的有序区间拷贝回原数组，完成当前轮次排序。
边界处理：适配非2的幂次数组 若数组长度不是2*gap的整数倍，最后一组可能不完整：

第二子组起始位置超数组长度（如数组长度5、gap=2时，最后一组仅[4]），则跳过该组；
第二子组结束位置超数组长度（如数组长度5、gap=2时，第二子组本应[4,5]），则将结束位置修正为数组最后一个元素的下标。

（4）代码实现

// 非递归实现归并排序
// a: 待排序数组首地址，n: 数组元素个数
void MergeSortNonR(int* a, int n)
{
    // 动态开辟临时数组，用于暂存归并结果（避免原数组数据覆盖）
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)  // 内存开辟失败处理
    {
        perror("malloc fail");  // 打印错误信息
        return;
    }

    // gap：当前每一组待归并的子数组长度（初始为1，单个元素天然有序）
    int gap = 1;
    // 当gap小于数组长度时，继续归并（gap >=n 时数组已完全有序）
    while (gap < n)
    {
        // 遍历数组，每次处理2*gap长度的区间（两组gap长度的子数组）
        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;  // 第二组区间

            // 打印当前处理的两组区间（用于调试观察分组情况）
           // printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

            // 边界处理1：第二组起始位置越界（第二组不存在），无需归并，直接跳出
            if (begin2 >= n)
                break;

            // 边界处理2：第二组结束位置越界，修正为数组最后一个元素下标
            if (end2 >= n)
                end2 = n - 1;

            // j：临时数组tmp的起始写入位置（与原数组i位置对齐）
            int j = i;
            // 双指针归并：合并两个有序子数组到tmp
            while (begin1 <= end1 && begin2 <= end2)
            {
                // 取较小元素存入tmp，对应指针后移
                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++];
            }

            // 将tmp中合并好的有序区间拷贝回原数组a的对应位置
            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
        }

        //printf("\n");  // 每轮gap处理完换行，方便调试观察分组结果
        gap *= 2;  // gap倍增，下一轮处理更长的有序子数组
    }

    free(tmp);  // 释放临时数组，避免内存泄漏
    tmp = NULL; // 防止野指针
}

验证非递归

int main()
{
    int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
	MergeSortNonR(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
    //TestOP();
    return 0;
}

结果均正确

4、时间复杂度

归并排序递归和非递归版本的时间复杂度完全一样，都是

O(n\log n)

。原因很简单：两者本质都是“分组合并”，需要

\log n

层合并，每层合并都要遍历

个元素，总操作量就是

n\log n

，只是实现方式（递归/迭代）不同而已。

5、归并排序特性

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)

6、四大排序对比

又到了排序性能对比的时候啦，这次四大排序进行对比

#include"Sort.h"
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		// ÖØ¸´²»¶à
		a1[i] = rand() + i;
		// ÖØ¸´½Ï¶à
		//a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	//PrintArray(a2, N);

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	BubbleSort(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}
int main()
{
    /*int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
	MergeSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));*/
    TestOP();
    return 0;
}

我们可以看出冒泡和直接选择排序最慢，插入好点，其他4个挺快

7、总代码

这里就不把栈和队列的代码展示出来啦！ Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
//直接插入排序
void InsertSort(int* a, int n);
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n);
//打印
void PrintArray(int* a, int n);
//交换
void Swap(int* p1, int* p2);
//直接选择排序
void SelectSort(int* a, int n);
//堆排序
void HeapSort(int* a, int n);
//向下调整建堆
void AdjustDown(int* a, int n, int parent);
//冒泡排序
void BubbleSort(int* a, int n);
//快速排序
void QuickSort(int* arr, int left, int right);
//三数取中法
int GetMidi(int* a, int left, int right);
//hoare快排
int PartSort1(int* a, int left, int right);
//lomuto前后指针实现快排
int PartSort2(int* a, int left, int right);
// 挖坑法单趟排序（结合三数取中）
int PartSort3(int* a, int left, int right);
//用栈模拟快速排序
void QuickSortNonR(int* a, int left, int right);
// 用队列实现快速排序（非递归）
void QuickSortNonR2(int* a, int left, int right);
// 递归实现归并排序
void _MergeSort(int* a, int* tmp, int begin, int end);
void MergeSort(int* a, int n);
//非递归实现归并排序
void MergeSortNonR(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
//直接插入排序
void InsertSort(int* a, int n)
{
    //  [0, n-1]
    for (int i = 0; i < n - 1; i++)
    {
        // [0, n-2]是最后一组
        // [0,end]有序 end+1位置的值插入[0,end]，保持有序
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            //升序大于>,降序小于
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        // +1保证最后一个gap一定是1
        // gap > 1时是预排序
        // gap == 1时是插入排序
        gap = gap / 3 + 1;

        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}
//打印
void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;

    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }

            if (a[i] < a[mini])
            {
                mini = i;
            }
        }

        Swap(&a[begin], &a[mini]);
        if (begin == maxi)
            maxi = mini;
        Swap(&a[end], &a[maxi]);
        ++begin;
        --end;
    }
}
//向下调整建堆
void AdjustDown(int* a, int n, int parent)
{
    // 先假设左孩子小
    int child = parent * 2 + 1;

    while (child < n)  // child >= n说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }

        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//堆排序
void HeapSort(int* a, int n)
{
    // 向下调整建堆 O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}
// O(N^2) 最坏
 // O(N)   最好
//冒泡排序
void BubbleSort(int* a, int n)
{
    for (int j = 0; j < n; j++)
    {
        // 单趟
        int flag = 0;
        for (int i = 1; i < n - j; i++)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                flag = 1;
            }
        }

        if (flag == 0)
        {
            break;
        }
    }
}
//三数取中法
int GetMidi(int* a, int left, int right)
{
    int midi = (left + right) / 2;
    // left midi right
    if (a[left] < a[midi])
    {
        if (a[midi] < a[right])
        {
            return midi;
        }
        else if (a[left] < a[right])
        {
            return right;
        }
        else
        {
            return left;
        }
    }
    else // a[left] > a[midi]
    {
        if (a[midi] > a[right])
        {
            return midi;
        }
        else if (a[left] < a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}
//hoare快排
int PartSort1(int* a, int left, int right)
{
    // 三数取中
    int midi = GetMidi(a, left, right);
    Swap(&a[left], &a[midi]);

    int keyi = left;
    int begin = left, end = right;
    while (begin < end)
    {
        // 右边找小
        while (begin < end && a[end] >= a[keyi])
        {
            --end;
        }

        // 左边找大
        while (begin < end && a[begin] <= a[keyi])
        {
            ++begin;
        }

        Swap(&a[begin], &a[end]);
    }

    Swap(&a[keyi], &a[begin]);
    return begin;
}
//lomuto前后指针实现快排
int PartSort2(int* a, int left, int right)
{
    int midi = GetMidi(a, left, right); //三数取中
    Swap(&a[left], &a[midi]);//将中间值与开头进行交换来作为key
    int keyi = left;

    //lomuto前后指针(单趟)
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi]&&++prev!=cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;

}
// 挖坑法单趟排序（结合三数取中）
int PartSort3(int* a, int left, int right) 
{
    // 三数取中优化：选中位数作为基准，交换到left位置
    int midIdx = GetMidi(a, left, right);
    Swap(&a[left], &a[midIdx]); // 将中位数换到left，作为基准

    int key = a[left]; // 基准值
    int pit = left;    // 初始坑位

    while (left < right)
    {
        // 右指针找比key小的元素，填左坑
        while (left < right && a[right] >= key) 
        {
            --right;
        }
        a[pit] = a[right];
        pit = right; // 更新坑位

        // 左指针找比key大的元素，填右坑
        while (left < right && a[left] <= key)
        {
            ++left;
        }
        a[pit] = a[left];
        pit = left; // 更新坑位
    }

    a[pit] = key; // 基准值填入最终坑位
    return pit;   // 返回基准位置
}
// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
// 后续讲一下思路即可
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;

    // 小区间优化，不再递归分割排序，减少递归的次数
    if ((right - left + 1) < 10)
    {
        InsertSort(a + left, right - left + 1);
    }
    else
    {
        //int keyi = PartSort1(a, left, right);
        int keyi = PartSort2(a, left, right);
       // int keyi = PartSort3(a, left, right);
        // [left, keyi-1] keyi [keyi+1, right]
        QuickSort(a, left, keyi - 1);
        QuickSort(a, keyi + 1, right);
    }
}
#include"Stack.h"
//用栈模拟快速排序
void QuickSortNonR(int* a, int left, int right)
{
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);

    while (!STEmpty(&st))
    {
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);
        // 小区间优化：长度<10时用插入排序，跳过后续分治
        if (end - begin + 1 < 10) 
        {
            InsertSort(a + begin, end - begin + 1); // a+begin指向区间起始位置
            continue; // 跳过后面的PartSort和入栈，处理下一个栈内区间
        }
        int keyi = PartSort2(a, begin, end);
        // [begin, keyi-1] keyi [keyi+1, end]
        if (keyi + 1 < end)
        {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }

        if (begin < keyi - 1)
        {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }

    STDestroy(&st);
}
#include"Queue.h"
// 用队列实现快速排序（非递归）
void QuickSortNonR2(int* a, int left, int right)
{
    Queue qe;
    QueueInit(&qe);
    QueuePush(&qe, left);//先进先出先加左边
    QueuePush(&qe, right);
    while (!QueueEmpty(&qe))
    {
        int begin = QueueFront(&qe);
        QueuePop(&qe);
        int end = QueueFront(&qe);
        QueuePop(&qe);
        // 小区间优化：长度<10时用插入排序，跳过后续分治
        if (end - begin + 1 < 10)
        {
            InsertSort(a + begin, end - begin + 1); // a+begin指向区间起始位置
            continue; // 跳过后面的PartSort和入栈，处理下一个栈内区间
        }
        int key = PartSort1(a, begin, end);
        if (key - 1 > begin)//如果左存在先压左
        {
            QueuePush(&qe, begin);
            QueuePush(&qe, key - 1);
        }
        if (key + 1 < end)//如果右存在先压右
        {
            QueuePush(&qe, key + 1);
            QueuePush(&qe, end);
        }
    }
    QueueDestroy(&qe);

}
// 时间复杂度：O(N * logN)
// 空间复杂度：O(N)
// 递归实现归并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{
    if (begin >= end)
        return;

    int mid = (begin + end) / 2;
    // 如果[begin, mid][mid+1, end]有序就可以进行归并了
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);//分解过程

    // 归并
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin;
    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 + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    _MergeSort(a, tmp, 0, n - 1);

    free(tmp);
    tmp = NULL;
}
void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    // gap每组归并数据的数据个数
    int gap = 1;
    while (gap < n)
    {
        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;

            //printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

            // 第二组都越界不存在，这一组就不需要归并
            if (begin2 >= n)
                break;

            // 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
            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));
        }

        //printf("\n");

        gap *= 2;
    }

    free(tmp);
    tmp = NULL;
}

test.c

#include"Sort.h"
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		// ÖØ¸´²»¶à
		a1[i] = rand() + i;
		// ÖØ¸´½Ï¶à
		//a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	//PrintArray(a2, N);

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	BubbleSort(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}
int main()
{
    /*int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
	MergeSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));*/
    TestOP();
    return 0;
}