http://archive.cnblogs.com/a/1773844/
對(duì)文件內(nèi)數(shù)據(jù)排序時(shí)，如果文件較小，可以將文件內(nèi)數(shù)據(jù)全部讀入內(nèi)存時(shí)，通過(guò)內(nèi)排序方法如冒泡，快速排序等方法，可以很方便的實(shí)現(xiàn)。
但如果文件大小超過(guò)了內(nèi)存大小，僅僅使用內(nèi)排序就不能達(dá)到目標(biāo)了。
解決這個(gè)問(wèn)題，有一個(gè)方法是大名鼎鼎的外排序：將大文件分成若干個(gè)小文件，對(duì)小文件進(jìn)行內(nèi)排序，然后將各個(gè)有序小文件組合成大的有序文件。外排序方法需要反復(fù)的讀寫(xiě)文件，時(shí)間復(fù)雜度較高。
下面的代碼使用的是win32API提供的文件映射內(nèi)存方法，能減少文件讀寫(xiě)次數(shù)，提高效率。
/**
說(shuō)明：程序首先生成由隨機(jī)整數(shù)組成的文件，然后利用文件映射內(nèi)存訪問(wèn)數(shù)據(jù)，將數(shù)據(jù)進(jìn)行升序排序后輸出的另一個(gè)文件。
*/
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <Windows.h>
#include <string>
using namespace std;
#define ORIGIN_FILE_NAME "data" //數(shù)據(jù)文件名
#define NUMBER_COUNT 1024 //隨機(jī)生成的整數(shù)數(shù)量
int GenerateOriginDataFile();//生成數(shù)據(jù)文件：由n個(gè)隨機(jī)整數(shù)組成
int SortFile();//文件排序
int main()
{
GenerateOriginDataFile();
DWORD dwStart = GetTickCount();
SortFile();
DWORD dwEnd = GetTickCount();
cout << "running time spend:" << dwEnd - dwStart << endl;
return 0;
}
int SortFile()
{
// 創(chuàng)建文件對(duì)象
HANDLE hFile = CreateFile(ORIGIN_FILE_NAME, GENERIC_READ | GENERIC_WRITE,
0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
if (hFile == INVALID_HANDLE_VALUE)
{
printf("創(chuàng)建文件對(duì)象失敗,錯(cuò)誤代碼:%drn", GetLastError());
return -1;
}
// 創(chuàng)建文件映射對(duì)象
HANDLE hFileMap = CreateFileMapping(hFile, NULL, PAGE_READWRITE, 0, 0, NULL);
if (hFileMap == NULL)
{
printf("創(chuàng)建文件映射對(duì)象失敗,錯(cuò)誤代碼:%drn", GetLastError());
return -1;
}
// 得到系統(tǒng)分配粒度
SYSTEM_INFO SysInfo;
GetSystemInfo(&SysInfo);
DWORD dwGran = SysInfo.dwAllocationGranularity;
// 得到文件尺寸
DWORD dwFileSizeHigh;
__int64 qwFileSize = GetFileSize(hFile, &dwFileSizeHigh);
qwFileSize |= (((__int64)dwFileSizeHigh) << 32);
// 關(guān)閉文件對(duì)象
CloseHandle(hFile);
// 偏移地址
__int64 qwFileOffset = 0;
// 塊大小
DWORD dwBlockBytes = 1000 * dwGran;
if (qwFileSize < 1000 * dwGran)
dwBlockBytes = (DWORD)qwFileSize;
while (qwFileSize > 0)
{
// 映射視圖
LPBYTE lpbMapAddress = (LPBYTE)MapViewOfFile(hFileMap,FILE_MAP_ALL_ACCESS,
(DWORD)(qwFileOffset >> 32), (DWORD)(qwFileOffset & 0xFFFFFFFF),
dwBlockBytes);
if (lpbMapAddress == NULL)
{
printf("映射文件映射失敗,錯(cuò)誤代碼:%drn", GetLastError());
return -1;
}
const int NUMBER_MAX_LENGTH = 6;
// 對(duì)映射的視圖進(jìn)行訪問(wèn)
char temp[NUMBER_MAX_LENGTH + 1] = {0};
int number = 0;
//直接操作內(nèi)存lpbMapAddress，進(jìn)行冒泡排序
for(DWORD i = 0; i < dwBlockBytes; i+=NUMBER_MAX_LENGTH)
{
for (int j=0;j<NUMBER_MAX_LENGTH;j++)
{
temp[j] = *(lpbMapAddress + i + j);
}
number = atoi(temp);
for (int j=i+NUMBER_MAX_LENGTH;j<dwBlockBytes;j+=NUMBER_MAX_LENGTH)
{
for (int k=0;k<NUMBER_MAX_LENGTH;k++)
{
temp[k] = *(lpbMapAddress + j + k);
}
if (number > atoi(temp))
{
for (int k=0;k<NUMBER_MAX_LENGTH;k++)
{
*(lpbMapAddress + j + k) = *(lpbMapAddress + i + k);
*(lpbMapAddress + i + k) = temp[k];
}
number = atoi(temp);
}
}
}
// 撤消文件映像
UnmapViewOfFile(lpbMapAddress);
// 修正參數(shù)
qwFileOffset += dwBlockBytes;
qwFileSize -= dwBlockBytes;
}
// 關(guān)閉文件映射對(duì)象句柄
CloseHandle(hFileMap);
return 0;
}
int GenerateOriginDataFile()
{
FILE* pFile = fopen(ORIGIN_FILE_NAME,"w");
srand((unsigned)time(0));
for (int i=0;i<NUMBER_COUNT;i++)
{
long ran_num = rand();
fprintf(pFile,"%-5d ",ran_num);
}
fclose(pFile);
return 0;
}