c++ - 使用 Shell 排序对文件进行就地排序

Question

有人要求我使用 shell 排序就地对文件进行排序(也可以使用快速排序，但我认为如果我找到一种方法，我将能够同时进行这两种排序)。我一直在想什么可能会有所帮助，但我找不到办法去做。我有一个数组的算法，但我想不出一种方法让它与文件一起工作。

有什么办法可以做到这一点吗？

编辑:

在 André Puel 发布的代码的帮助下，我能够编写一些目前可用的代码，如果你想检查它，可以在这里查看:

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <sstream>
using namespace std;

int toNum(const string &s) {
  stringstream ss(s);
  int n;
  ss >> n;
  return n;
}

string toStr(int n) {
  stringstream ss;
  ss << n;
  string s;
  ss >> s;
  return string(5 - s.size(),' ') + s;
}

int getNum(fstream &f,int pos) {
  f.seekg(pos*5);
  string s;
  for(int i = 0; i < 5; ++i) s += f.get();
  return toNum(s);
}

void putNum(fstream &f, int pos,int n) {
  f.seekp(pos*5);
  f.write(toStr(n).c_str(),5);
}

int main() {
  fstream input("entrada1",fstream::in | fstream::out);
  string aux;
  getline(input,aux);
  int n = aux.size() / 5,temp,j;

  int gaps[] = {701,301,132,57,23,10,4,1};
  int g = sizeof(gaps)/sizeof(gaps[0]);
  for(int k = 0; k < g; ++k) {
    for(int i = k; i < n; ++i) {
      temp = getNum(input,i);
      for(j = i; j >= k and getNum(input,j - k) > temp; j -= k) {
        putNum(input,j,getNum(input,j - k));
      }
      putNum(input,j,temp);
    }
  }
  input.close();
  return 0;
}

Answer 1

当您在 C++ 中打开一个文件时，您有两个指针。 setter/getter 指针和推杆指针。它们指示您正在文件中写入和读取的位置。

使用 seekp , 你可以告诉你想写的地方。使用 tellp你知道你要写的地方。每次您写东西时，推杆指针都会自动前进。

getter指针也一样，函数是seekg和 tellg .

使用这些操作，您可以轻松地模拟数组。让我向您展示一些代码:

class FileArray {
public:
    FileArray(const char* path) 
    : file(path, std::fstream::app|std::fstream::binary)
    {
        file.seekg(0,std::fstream::end);
        size = file.tellg();
    }

    void write(unsigned pos, char data) {
        assert(pos < size );
        file.tellp(pos);
        file.put(data);
    }

    char read(unsigned pos) {
        assert(pos < size);
        file.seekg(pos);
        return file.get();
    }
private:
    std::fstream file;
    std::size_t size;
}

这是一种处理文件的简单方法，因为您假设是随机访问。好吧，随机访问是真的，但它可能很慢。当您访问彼此靠近(空间局部性)的数据时，文件流工作得更快。

虽然这是开始处理您的问题的好方法，但如果您对文件 IO 有了经验，您将最终找到提高特定问题性能的方法。让我们保持婴儿的步伐。

我要您注意的另一件事是，当您执行写入时，数据会重定向到将写入文件的 fstream。我知道内核会尝试缓存这些东西，并优化速度，但如果你有某种缓存层来避免直接写入磁盘仍然会更好。

最后，我假设您正在处理字符(因为它会更容易)，但您可以处理其他数据类型，您只需要注意索引和数据类型的大小。例如，long long 类型确实有 8 个字节的大小，如果您想访问您的 file-array 中的第一个元素，您将访问位置 8*0，并且你将不得不阅读 8 个字节。如果你想要第 10 个元素，你将访问位置 8*10 并再次读取 8 个字节的数据以构造 long long 值。