归并外排序实现

1. 归并外排序实现

归并排序实现文件排序，对小文件排序是没有意义的，最终目的是为了排序大文件，我们这里100个数据只是进行模拟。

效果图：

2. ExternalSort.c

文件存储数据要么以空格间隔，要么换行，我们有3个系列函数可以进行处理。

scanf(读取控制台)、fscanf(读取文件)、sscanf(读取字符串).

printf(写到控制台)、fprintf(写到文件)、sprintf(写到字符串).

如果数据存储的不规范那就麻烦了，通常情况下都是规范的。

我们这里模拟的问题是：假设有海量数据待排序，那么数据一般在文件中，我们假设这个海量数据无法加载到内存当中，内存没有那么大。那怎么办呢？

我们这里就需要归并，把文件分成一段一段的数据，对每一段数据进行排序(这里使用快排)再写进小文件，最后对每一个小文件进行归并。归并的对象可以是数组，也可以是文件。但是必须保证要开一个O(n)的空间，所以它是很消耗存储空间的。但是文件不能支持随机访问，即使强制使用文件指针，效率也是很低下的。

我们这里的归并是依次读取每一段排序后的文件进行归并，不需要随机访问，效率相对而言较优。

分割数据排序的过程在内存，归并的过程在磁盘。

分布式数据就更复杂了。我们这里的代码就能够应付绝大多数情况了。

归并的过程：file1、file2、mfile存储的是文件名。

#define _CRT_SECURE_NO_WARNINGS 1
#include "ExternalSort.h"

void _MergeSortFile(const char* file1, const char* file2, const char* mfile)
{
    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(mfile, "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(fscanf(fout1,"%d\n", &num1) != EOF
       && fscanf(fout2,"%d\n", &num2) != EOF)*/
    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);//保证谁归并后谁的文件指针往后动
        }
    }

    //这里还是按之前的方式写就不会漏掉最后一个数据
    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("打开文件失败\n");
        exit(-1);
    }

    // 分割成一段一段数据,内存排序后写到小文件
    int n = 10;//模拟:100个数据切成10份
    int a[10];//每个文件10个数据
    int i = 0;
    int num = 0;
    char subfile[20];
    int filei = 1;

    memset(a, 0, sizeof(int) * n);
    //从fout中一次读取10个数据
    while (fscanf(fout, "%d ", &num) != EOF)
    {
        //if(i < n) 这样写fscanf文件下标会自动走到第11个数据，导致每次读取会丢失一个数据
        if (i < n - 1)
        {
            a[i++] = num;
        }
        else
        {
            a[i] = num;//第10个数据在这里单独处理
            QuickSort(a, 0, n - 1);
            //在subfile中存储文件名,文件名为1,2,3...
            sprintf(subfile, "%d", filei++);
            FILE* fin = fopen(subfile, "w");//创建0号文件,再把排序好的第一份数据写入，不断迭代。
            if (fin == NULL)
            {
                printf("打开文件失败\n");
                exit(-1);
            }
            for (int i = 0; i < n; i++)
            {
                fprintf(fin, "%d\n", a[i]);//自动转字符串
            }
            fclose(fin);

            i = 0;
            memset(a, 0, sizeof(int) * n);
        }
    }
    // 利用互相归并到文件，实现整体有序
    char mfile[100] = "12";
    char file1[100] = "1";
    char file2[100] = "2";
    for (int i = 2; i <= n; ++i)
    {
        //读取file1和file2进行归并出mfile
        _MergeSortFile(file1, file2, mfile);

        strcpy(file1, mfile);
        sprintf(file2, "%d", i + 1);
        sprintf(mfile, "%s%d", mfile, i + 1);
    }

    fclose(fout);
}

int main()
{
    MergeSortFile("D:\\练习\\ExternalSort\\sub.txt");

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

3. ExternalSort.h

#pragma once
#include 
#include 
#include 
#include 


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		// 单趟排序：[0, end]有序 end+1位置的值，插入进入，保持他依旧有序
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + (right - left) / 2;
	// left mid right
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

// 前后指针法
int PartSort(int* a, int left, int right)
{
	//int midi = GetMidIndex(a, left, right);
	//Swap(&a[midi], &a[left]);

	int keyi = left;
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && a[++prev] != a[cur])
			Swap(&a[prev], &a[cur]);

		++cur;
	}
	Swap(&a[prev], &a[keyi]);

	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	// 子区间相等只有一个值或者不存在那么就是递归结束的子问题
	if (begin >= end)
		return;

	// 小区间直接插入排序控制有序
	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort(a, begin, end);
		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}


	if (begin >= end)
		return;

	// 小区间直接插入排序控制有序
	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort(a, begin, end);
		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140