cpp外排序示例
时间: 2023-07-01 07:04:58 浏览: 51
下面是一个基于C++的外部排序示例程序。外部排序是一种在内存不足以容纳全部数据时进行排序的技术,它将数据分成多个部分进行排序,然后将这些部分逐一合并,直到最终得到有序的结果。
示例程序中使用的是归并排序算法,它可以处理大量数据并且具有较好的稳定性。
```
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_BUFFER_SIZE = 1000000; // 缓存区大小
const string INPUT_FILE_NAME = "input.txt"; // 输入文件名
const string OUTPUT_FILE_NAME = "output.txt"; // 输出文件名
// 读取指定长度的数据
vector<int> read_data(ifstream& ifs, int count) {
vector<int> data(count);
for (int i = 0; i < count; i++) {
ifs >> data[i];
}
return data;
}
// 将数据写入输出文件
void write_data(ofstream& ofs, const vector<int>& data) {
for (int i = 0; i < data.size(); i++) {
ofs << data[i] << endl;
}
}
// 归并排序
void merge_sort(const vector<string>& chunk_files) {
vector<ifstream> chunk_ifs(chunk_files.size());
vector<vector<int>> chunks(chunk_files.size());
// 打开所有输入文件
for (int i = 0; i < chunk_files.size(); i++) {
chunk_ifs[i].open(chunk_files[i]);
chunks[i] = read_data(chunk_ifs[i], MAX_BUFFER_SIZE / chunk_files.size());
}
// 打开输出文件
ofstream ofs(OUTPUT_FILE_NAME);
// 循环合并
while (true) {
// 找到最小的数
int min_val = INT_MAX;
int min_idx = -1;
for (int i = 0; i < chunks.size(); i++) {
if (!chunks[i].empty() && chunks[i][0] < min_val) {
min_val = chunks[i][0];
min_idx = i;
}
}
// 如果所有数据都已经处理完,则退出循环
if (min_idx == -1) {
break;
}
// 将最小的数写入输出文件
ofs << min_val << endl;
chunks[min_idx].erase(chunks[min_idx].begin());
// 如果当前 chunk 已经处理完,则从输入文件中读取新的数据
if (chunks[min_idx].empty()) {
chunks[min_idx] = read_data(chunk_ifs[min_idx], MAX_BUFFER_SIZE / chunk_files.size());
}
}
// 关闭所有文件
for (int i = 0; i < chunk_ifs.size(); i++) {
chunk_ifs[i].close();
}
ofs.close();
}
// 分割文件并排序
void sort_file() {
ifstream ifs(INPUT_FILE_NAME);
int chunk_count = 0;
vector<int> buffer(MAX_BUFFER_SIZE);
// 循环读取数据并排序
while (true) {
int count = 0;
while (count < MAX_BUFFER_SIZE && ifs >> buffer[count]) {
count++;
}
// 如果没有数据了,则退出循环
if (count == 0) {
break;
}
// 排序并将数据写入 chunk 文件
sort(buffer.begin(), buffer.begin() + count);
string chunk_file_name = "chunk_" + to_string(chunk_count++) + ".txt";
ofstream ofs(chunk_file_name);
write_data(ofs, vector<int>(buffer.begin(), buffer.begin() + count));
}
// 关闭输入文件
ifs.close();
// 归并所有 chunk 文件
vector<string> chunk_files(chunk_count);
for (int i = 0; i < chunk_count; i++) {
chunk_files[i] = "chunk_" + to_string(i) + ".txt";
}
merge_sort(chunk_files);
// 删除所有 chunk 文件
for (int i = 0; i < chunk_count; i++) {
remove(("chunk_" + to_string(i) + ".txt").c_str());
}
}
int main() {
sort_file();
return 0;
}
```
以上程序实现了一个简单的外部排序,它的基本思路是将大文件划分成多个小文件,然后对每个小文件进行排序,最后再将所有小文件归并成一个有序的结果。在实际应用中,可能需要对其中的一些细节进行优化,以提高排序效率。