归并排序

        插入、选择、交换排序更擅长做“内排序”，而归并排序更擅长做“外排序”。

基本思想：

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

1. 归并排序递归实现

        归并排序的思想我们已经明白了，但我们实际操作的时候不能每次分解都malloc出来一个空间，这样会导致大量碎片空间的出现，所以我们就创建tmp临时空间，每次归并都在tmp中进行。

/* 归并排序递归实现 */
/* left：左下标 right：右下标 */
/* tmp：归并所需的临时空间 */
/* 时间复杂度：O(N*log(2)N) */
/* 空间复杂度：O(N) */
void _MergeSort(int* a, int left, int right, int* tmp)
{
        if (left >= right)
                return;

        int mid = (left + right) / 2;
        // [left,mid][mid+1,right]有序，则可以合并，现在没有序，子问题解决

        _MergeSort(a, left, mid, tmp);
        _MergeSort(a, mid + 1, right, tmp);


        // 归并[left,mid][mid+1,right]有序
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int index = begin1;
        while (begin1 <= end1 && begin2 <= end2)
        {
                if (a[begin1] < a[begin2])
                        tmp[index++] = a[begin1++];
                else
                        tmp[index++] = a[begin2++];
        }

        while (begin1 <= end1)
                tmp[index++] = a[begin1++];
        while (begin2 <= end2)
                tmp[index++] = a[begin2++];

        // 将归并好的数据拷贝回原数组
        for (int i = left; i <= right; i++)
        {
                a[i] = tmp[i];
        }
}

/* 归并排序递归实现 */
void MergeSort(int* a, int n)
{
        assert(a);

        int* tmp = (int*)malloc(sizeof(int) * n);

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

        free(tmp);
}

2. 归并排序非递归实现

        将一个递归改成非递归，上文有说，两种方法：1. 改循环 2. 使用模拟栈

        这里我们直接使用改循环的办法，但是需要注意，循环一定要注意边界问题，不然非常容易数组越界。

（下面代码中的归并数组函数是从递归实现的代码中抽象出来的）

/* 归并数组 */
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
        // 归并[left,mid][mid+1,right]有序
        int left = begin1, right = end2;

        int index = begin1;
        while (begin1 <= end1 && begin2 <= end2)
        {
                if (a[begin1] < a[begin2])
                        tmp[index++] = a[begin1++];
                else
                        tmp[index++] = a[begin2++];
        }

        while (begin1 <= end1)
                tmp[index++] = a[begin1++];
        while (begin2 <= end2)
                tmp[index++] = a[begin2++];

        // 将归并好的数据拷贝回原数组
        for (int i = left; i <= right; i++)
        {
                a[i] = tmp[i];
        }
}

/* 归并排序非递归实现 */
void MergeSortNonR(int* a, int n)
{
        assert(a);
        int* tmp = (int*)malloc(sizeof(int) * n);
        int gap = 1;
        while (gap < n)
        {
                for (int i = 0; i < n; i += 2 * gap)
                {
                        // [i, i+gap)[i+gap, i+2*gap)        开区间
                        // [i, i + gap -1][i + gap, i + 2 * gap - 1]        闭区间
                        // 这里使用和递归实现一样的闭区间来做
                        int begin1 = i, end1 = i + gap - 1;
                        int begin2 = i + gap, end2 = i + 2 * gap - 1;

                        // 需要注意处理边界问题
                        // 1.合并时只有第一组，就不需要合并
                        if (begin2 >= n)
                                break;
                        // 2.合并时第二组只有部分数据，需要修正end2边界
                        if (end2 >= n)
                                end2 = n - 1;

                        // 合并
                        MergeArr(a, begin1, end1, begin2, end2, tmp);
                }
                gap *= 2;
        }
        // 释放tmp临时空间
        free(tmp);
}

归并排序的特性总结：

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

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定

3. 外排序（对大量文件中数据排序）

        如果说文件中有10亿个数据，需要排序，怎么办？

        假设内存中最多只能放1000w个数据。

        那我们就把10亿个数据读出来，切分成100份文件。

        1号文件和2号文件一归，归并成12号文件，12号文件和3号文件一归，归并成123号文件...最后所有文件归并完后，得到的最终文件就是10亿个数据排序好的文件。

        也就是说我们要尽量把大文件平均分割成N份，这里的“N”由你自己决定，要保证每份的大小可以加载到内存，那么就可以把每个小文件加载到内存中，使用快排排成有序，再写回小文件。

/* 归并file1和file2到mfile */
void _MergeFile(FILE* file1, FILE* file2, FILE* mfile)
{
        FILE* fout1 = fopen(file1, "r");
        if (fout1 == NULL)
        {
                printf("打开文件失败\r\n");
                exit(-1);
        }

        FILE* fout2 = fopen(file2, "r");
        if (fout2 == NULL)
        {
                printf("打开文件失败\r\n");
                exit(-1);
        }

        FILE* fin = fopen(mfile, "w");
        if (fin == NULL)
        {
                printf("打开文件失败\r\n");
                exit(-1);
        }
        int num1, num2;
        int ret1 = fscanf(fout1, "%d\n", &num1);
        int ret2 = fscanf(fout2, "%d\n", &num2);
        while (ret1 != EOF && ret2 != EOF)
        {
                if (num1 < num2)
                {
                        fprintf(fin, "%d\n", num1);
                        ret1 = fscanf(fout1, "%d\n", &num1);
                }
                else
                {
                        fprintf(fin, "%d\n", num2);
                        ret2 = fscanf(fout2, "%d\n", &num2);
                }
        }
        // 最后肯定有个文件没读完，把没读完的文件的剩下的数据写进mfile
        while (ret1 != EOF)
        {
                fprintf(fin, "%d\n", num1);
                ret1 = fscanf(fout1, "%d\n", &num1);
        }
        while (ret2 != EOF)
        {
                fprintf(fin, "%d\n", num2);
                ret2 = fscanf(fout2, "%d\n", &num2);
        }

        fclose(fout1);
        fclose(fout2);
        fclose(fin);
}

/* 外排序对文件内数据排序 */
void MergeSortFile(const char* file)
{
        FILE* fout = fopen(file, "r");
        if (fout == NULL)
        {
                printf("打开文件失败\r\n");
                exit(-1);
        }

        // 分割成一段段数据，内存排序后写到小文件
        int n = 10;
        int num = 0;
        int i = 0;
        int a[10];
        int filei = 1;
        char subfile[20];
        // while每次读一个数据
        while (fscanf(fout, "%d\n", &num) != EOF)
        {
                // 前9个数据进数组
                if (i < n - 1)
                {
                        a[i++] = num;
                }
                else
                {
                        a[i++] = num;        // 第十个数据
                        QuickSort(a, 0, n - 1);
                        sprintf(subfile, "%d", filei++);
                        FILE* fin = fopen(subfile, "w");
                        if (fin == NULL)
                        {
                                printf("打开文件失败\n");
                                exit(-1);
                        }
                        for (int j = 0; j < n; j++)
                        {
                                fprintf(fin, "%d\n", a[j]);
                        }
                        fclose(fin);
                        i = 0;
                }
        }

        // 归并到文件，实现整体有序
        char mfile[100] = "12";
        char File1[100] = "1";
        char File2[100] = "2";
        // 从1到10号文件
        for (i = 2; i <= n; i++)
        {
                // File2从2号文件一直往后走，3号、4号...
                sprintf(File2,"%d", i);

                // 读取File1和File2，归并出mfile
                _MergeFile(File1, File2, mfile);

                // 让File1等于这次归并后的mfile
                strcpy(File1, mfile);
                // 拼下一次合并文件名（比如mfile是12，拼上3就是123）
                sprintf(mfile, "%s%d", mfile, i + 1);
        }

        fclose(fout);
}