language-agnostic - C#数据结构算法

Question

我最近接受了 TOP 软件公司之一的采访。我完全被面试官问我的一个问题困住了，那就是

问:我有一台 512 mb/1 GB RAM 的机器，我必须对 4 GB 大小的文件(XML 或任何文件)进行排序。我将如何进行？数据结构是什么，我将使用哪种排序算法以及如何使用？

你认为它可以实现吗？如果是，那么你能解释一下吗？

提前致谢!

Answer 1

这是在 C# 上模拟虚拟内存的一个示例

来源:http://msdn.microsoft.com/en-us/library/aa288465(VS.71).aspx

// indexer.cs
// arguments: indexer.txt
using System;
using System.IO;

// Class to provide access to a large file
// as if it were a byte array.
public class FileByteArray
{
    Stream stream;      // Holds the underlying stream
                        // used to access the file.
// Create a new FileByteArray encapsulating a particular file.
    public FileByteArray(string fileName)
    {
        stream = new FileStream(fileName, FileMode.Open);
    }

    // Close the stream. This should be the last thing done
    // when you are finished.
    public void Close()
    {
        stream.Close();
        stream = null;
    }

    // Indexer to provide read/write access to the file.
    public byte this[long index]   // long is a 64-bit integer
    {
        // Read one byte at offset index and return it.
        get 
        {
            byte[] buffer = new byte[1];
            stream.Seek(index, SeekOrigin.Begin);
            stream.Read(buffer, 0, 1);
            return buffer[0];
        }
        // Write one byte at offset index and return it.
        set 
        {
            byte[] buffer = new byte[1] {value};
            stream.Seek(index, SeekOrigin.Begin);
            stream.Write(buffer, 0, 1);
        }
    }

    // Get the total length of the file.
    public long Length 
    {
        get 
        {
            return stream.Seek(0, SeekOrigin.End);
        }
    }
}

// Demonstrate the FileByteArray class.
// Reverses the bytes in a file.
public class Reverse 
{
    public static void Main(String[] args) 
    {
        // Check for arguments.
        if (args.Length == 0)
        {
            Console.WriteLine("indexer <filename>");
            return;
        }

        FileByteArray file = new FileByteArray(args[0]);
        long len = file.Length;

        // Swap bytes in the file to reverse it.
        for (long i = 0; i < len / 2; ++i) 
        {
            byte t;

            // Note that indexing the "file" variable invokes the
            // indexer on the FileByteStream class, which reads
            // and writes the bytes in the file.
            t = file[i];
            file[i] = file[len - i - 1];
            file[len - i - 1] = t;
        }

        file.Close();
    } 
}

使用上面的代码滚动你自己的数组类。然后只需使用任何数组排序算法。