目录

1.排序的原理

1.1 保证子数组有序

1.2 时间复杂度

2. 递归实现

2.1 思路

2.2 代码

3. 非递归实现

3.1 思路

3.2 代码

4.面试题

4.1 题目

4.2 思路

---

       

1.排序的原理

归并排序是外排序，所谓外排序就是说能够对文件中的数据进行排序。

①首先，将待排序数组分成两部分，这两部分数组一定是有序的，使用两个指针分别初始化于这两部分的首元素；

②需要一个临时空间，两个指针指向的较小的元素先放入空数组中。

③如果选择其中一个指针的元素，那么该指针需要后移一位，如果没选到该元素，指针不动。

④如果其中一个数组元素被取完了，那么另外一个数组的内容直接填入空数组。

        上面的操作是建立在两部分数组是分别有序的情况下，但是我们如何保证两部分的数组是有序的呢？

1.1 保证子数组有序

                保证当前区间是有序的，如果该区间不是有序的，那么需要将该区间分成子区间，从而保证子区间有序，如果该区间只剩一个数，那么说明这个区间是有序的。

        将区间细分到只有一个数的时候，这就是递归的“归”，此时返回上一层的函数栈帧，使父区间变得有序。

1.2 时间复杂度

        这里可以将递归的过程当做二叉树的生成，每一层的节点是N，二叉树的高度是LogN，那么时间复杂度就可以计算出来是N*logN。

2. 递归实现

2.1 思路

①首先写一个归并排序的主函数，主函数需要创建一个临时变量tmp，用于存放排序的数据；

②调用归并排序的子函数，子函数需要传入原数组、区间、临时数组，子函数的目的是为了让区间内的数组有序。

③子函数：首先这是一个递归，需要写递归退出条件，即left >= right下标不合法或者就剩一个元素，说明是有序的，就退出递归。

④使用递归分别让左右区间分别有序。

⑤开始合并有序数组，begin指针指向的元素更小的存入tmp中。

⑥把tmp数组的元素拷贝回原数组。

2.2 代码

        

#include<stdio.h>// 使区间变得有序的方法
void _merge_sort(int* arr, int left, int right, int* tmp)
{// 递归退出条件if (left >= right){return;}// 求mid,将[left,right]分为[left,mid][mid+1,right]两部分int mid = (left + right) / 2;// 保证两区域是有序的才能进行合并有序数组_merge_sort(arr, left, mid, tmp);_merge_sort(arr, mid + 1, right, tmp);// 开始合并有序数组int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;// 记录tmp的下标int tmp_index = begin1;while (begin1 <= end1 && begin2 <= end2){// 两个有序数组，哪个小放哪个if (arr[begin1] < arr[begin2]){tmp[tmp_index++] = arr[begin1++];}else{tmp[tmp_index++] = arr[begin2++];}}// 退出的时候是某一数组已经取值完毕了while (begin1 <= end1){tmp[tmp_index++] = arr[begin1++];}while (begin2 <= end2){tmp[tmp_index++] = arr[begin2++];}// 将tmp数组的值全部放回arr去，进行覆盖for (int i = left; i <= right; ++i){arr[ i] = tmp[i];}
}void merge_sort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_merge_sort(arr, 0, n - 1, tmp);free(tmp);	
}

3. 非递归实现

3.1 思路

        使用循环，首先每一个元素作为一个单位进行排序，接下来两个一组为单位进行排序如下图所示：

最后按照四个元素一组进行排序，我们只需要控制间距即可。

3.2 代码

        首先写gap为1的时候，该如何操作，当gap为1的的时候，我们只需要将相邻两个元素进行合并操作，例如将10和6合并成6和10，下一次合并需要将7和1合并成1和7；以此类推。

        我们可以将合并有序数组这个方法单独抽象出来，然后后面直接调用此方法即可，下面的代码就是当gap=1的时候，书写的代码。

// 抽象合并有序数组的函数
void merge_array(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{int left = begin1, right = end2;// 记录tmp的下标int tmp_index = begin1;while (begin1 <= end1 && begin2 <= end2){// 两个有序数组，哪个小放哪个if (arr[begin1] < arr[begin2]){tmp[tmp_index++] = arr[begin1++];}else{tmp[tmp_index++] = arr[begin2++];}}// 退出的时候是某一数组已经取值完毕了while (begin1 <= end1){tmp[tmp_index++] = arr[begin1++];}while (begin2 <= end2){tmp[tmp_index++] = arr[begin2++];}// 将tmp数组的值全部放回arr去，进行覆盖for (int i = left; i <= right; ++i){arr[ i] = tmp[i];}
}void merge_sort_non(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;// 【i,i + gap - 1】和【i + gap,i + 2 * gap - 1】闭区间for (int i = 0; i < n; i+= 2*gap)// 1,2合并之后，i下一次要合并3,4,{merge_array(arr, i, i + gap - 1, i + gap, i + 2 * gap - 1, tmp);// gap=1的时候就是两个数合并}free(tmp);
}

我们可以验证一下，当gap=1的时候是否正确：

最后调整gap，外面增加一层循环，gap最多是n/2，每次循环gap需要变为原来的2倍，1,2,4.....

        这里需要注意的是，当gap不断变化，第二组有可能会出现越界的情况，下面需要标注第二组两种越界情况。

void merge_sort_non(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap <n){// 【i,i + gap - 1】和【i + gap,i + 2 * gap - 1】闭区间for (int i = 0; i < n; i += 2 * gap)// 1,2合并之后，i下一次要合并3,4,{// 确保不越界int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;// 确保不越界if (begin2 >= n) break;  // 第二个数组不存在if (end2 >= n) end2 = n - 1;  // 调整第二个数组的结束位置merge_array(arr, begin1, end1, begin2, end2, tmp);}gap *= 2;}free(tmp);
}

gap其实就是决定有多少个数进行合并，gap为1的时候，其实就是1个数和1个数进行合并。

4.面试题

4.1 题目

        ①文件有10亿个数据，需要排序，怎么办？假设内存中最多只能放1000w个数据。

首先将数据分成100份，一份就是1000w个数据，将每一份数据两两归并排序成一个文件（磁盘）

假设文件中的数据是按照换行来分割的：

首先需要将数据分成n等份，每一份的大小刚好可以存入内存里，然后对每一份进行排序，生成n份文件。

// 外排序,返回一个文件名
void file_sort(char* file)
{FILE* fout = fopen(file, "r");if (fout == NULL){printf("文件打开失败\n");exit(-1);}int num = 0;int n = 10;// 将文件内容分成10份int arr[10];// 临时存10个数int i = 0;char subfile[20];// 子文件名称int id = 0; // 子文件下标while (fscanf(fout, "%d\n", &num) != EOF){if (i < n){arr[i++] = num;}else{// 满10个了就排序merge_sort(arr, n);sprintf(subfile, "sub\\subfile_%d.txt", id++);printf("%s", subfile);// 对每一个文件进行写FILE* fin = fopen(subfile, "w");for (int i = 0; i < n; i++){fprintf(fin, "%d\n", arr[i]);}fclose(fin);i = 0;}}fclose(fout);}int main()
{file_sort("sort.txt");}

然后对这n份文件进行合并，实现整体有序，两两合并，可以如下图也可以两两等分合并。

思路就是，有两个小文件file1、file2作为临时变量，首先合并形成m_file，然后将fiel2后移一位到下一个文件，file1变成m_file，继续合并形成新的m_file。

4.2 思路

①每n个数据为一组（这里n=10），读到n个的时候进行排序创建一个文件，那么100个数据就会有10个文件1-10；每一个文件需要先排序再写入。

②使用三个变量，file1、file2、m_file用于存储文件名，file1和file2合并之后写死文件名为12；后面将合并后的数据给file1，修改m_file的文件名为：之前的文件名+i（当前下标+1，i从2开始），使其命名能够逐步增加。

③依次迭代1+2的数据称为新的file1再和迭代后新的file2继续合并，最后的结果就是10个文件的最终排序结果。

void _merge_file(const char* file1, const char* file2, const char* m_file)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){printf("文件打开失败\n");exit(-1);}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){printf("文件打开失败\n");exit(-1);}FILE* fin = fopen(m_file, "w");if (fin == NULL){printf("文件打开失败\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){// nums1写到m_filefprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);// fiel1的指针后移}else{fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);// fiel1的指针后移}}// 其中一个结束，另外一个按序写入while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);// fiel1的指针后移}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);// fiel1的指针后移}fclose(fin);fclose(fout1);fclose(fout2);
}// 外排序,返回一个文件名
void file_sort(char* file)
{FILE* fout = fopen(file, "r");if (fout == NULL){printf("文件打开失败\n");exit(-1);}int num = 0;int n = 10;// 将文件内容分成10份int arr[10];// 临时存10个数int i = 0;char subfile[20];// 子文件名称int id = 1; // 子文件下标while (fscanf(fout, "%d\n", &num) != EOF){if (i < n - 1) // 前n-1个数据{arr[i++] = num;}else{// 第十个arr[i] = num;// 满10个了就排序merge_sort(arr, n);sprintf(subfile, "%d", id++);printf("%s", subfile);// 对每一个文件进行写FILE* fin = fopen(subfile, "w");for (int i = 0; i < n; i++){fprintf(fin, "%d\n", arr[i]);}fclose(fin);i = 0;}}fclose(fout);// 读取两个文件char file1[100] = "1";char file2[100];char m_file[100] = "12"; // 合并的文件for (int i = 2; i <= n; i++){sprintf(file2, "%d.txt", i);// 读取file1和file2，将合并内容放到m_file_merge_file(file1, file2, m_file);// file1变成mfilestrcpy(file1,m_file);sprintf(m_file, "%s%d", m_file,i+1); // 拼接}}int main()
{file_sort("sort.txt");}