如何在一个巨大的文本文件中对整数进行排序？

Question

问题陈述

我一次给出一个非常大的数字列表,我需要打印" 中位数 ".

更清楚的是,可以有" 125,000,000 "数字,并保证每个数字小于" 1.e + 18 ".

这是一场比赛,因此有内存限制(20 MB顶部)和时间限制(5秒顶部).

" 中位数 "是排序数字中间的数字.
例如,如果这是数字列表:

23
8
16
42
15
4
108

排序后的数字:

1) 4
2) 8
3) 15
4) 16
5) 23
6) 42
7) 108

" 中位数 "将是16;

所以我在互联网上搜索它,但我找不到任何通过这些限制的答案.

---

途径

我的方法是获取所有数字,将它们保存在文本文件中,对它们进行排序,然后得到" 中位数 ".

---

思路

1. 我知道我可以从文件中读取所有数字并将它们放在矢量中,然后轻松地对它们进行排序.
   但这将超过内存限制.
   
   
2. 所以当我把它们放在文本文件中时,我提出了这个想法来对数字进行排序.
   这就像有一个循环,从控制台获取下一个数字后读取文件(逐行),当它到达正确的位置时,在那里插入数字,不接触其他数字.
   但问题是我不能在文本文件的中间插入一行,因为它会覆盖其他数字.
   
   
3. 所以我创建了两个文件,其中一个已经输入了数字,另一个读取了第一个文件,并将其自身的数字复制到正确的位置,然后插入最后给定的数字,然后继续复制剩余的数字.
   但它花费了太多时间,因此超出了时间限制.
   

---

请求

因此,我想要优化其中一个想法,以便通过限制或通过这些限制的任何新想法.

---

偏爱

我更喜欢使用第二个想法,因为与其他两个不同,它通过限制,但我不能这样做,因为我不知道如何在文本文件的中间插入一行.因此,如果我了解这一点,其余的过程将非常简单.

---

试图解决方案

这是一个接收数字的函数,通过读取文件,找到它的最佳位置并将其放在那里.
事实上,它代表了我的第三个想法.
所以它有效(我用很多输入测试了它)但是我之前提到的问题是时间限制.

void insertNewCombinedNumber ( int combinedNumber )
{
    char combinedNumberCharacterArray[ 20 ];
    bool isInserted = false;

    ofstream combinedNumbersOutputFile;
    ifstream combinedNumbersInputFile;

    // Operate on First File
    if ( isFirstCombinedFileActive )
    {
        combinedNumbersOutputFile.open ( "Combined Numbers - File 01.txt" );
        combinedNumbersInputFile.open ( "Combined Numbers - File 02.txt" );
    }
    // Operate on Second File
    else
    {
        combinedNumbersOutputFile.open ( "Combined Numbers - File 02.txt" );
        combinedNumbersInputFile.open ( "Combined Numbers - File 01.txt" );
    }

    if ( !combinedNumbersInputFile )
    {
        combinedNumbersInputFile.close ();

        ofstream combinedNumbersInputCreateFile ( "Combined Numbers - File 02.txt" );
        combinedNumbersInputCreateFile.close ();

        combinedNumbersInputFile.open ( "Combined Numbers - File 02.txt" );
    }

    combinedNumbersInputFile.getline ( combinedNumberCharacterArray , 20 );

    for ( int i = 0; !combinedNumbersInputFile.eof (); i++ )
    {
        if ( !isInserted && combinedNumber <= characterArrayToDecimal ( combinedNumberCharacterArray ) )
        {
            combinedNumbersOutputFile << combinedNumber << endl;
            isInserted = true;
        }

        combinedNumbersOutputFile << combinedNumberCharacterArray << endl;

        combinedNumbersInputFile.getline ( combinedNumberCharacterArray , 20 );
    }

    if ( !isInserted )
    {
        combinedNumbersOutputFile << combinedNumber << endl;
        isInserted = true;
    }

    isFirstCombinedFileActive = !isFirstCombinedFileActive;

    combinedNumbersOutputFile.close ();
    combinedNumbersInputFile.close ();
}

Answer 1

您真正需要的是针对此类问题的分而治之算法。查看外部排序中的外部合并排序和分布排序部分

其想法是将数据排序为多个块，然后使用分而治之的方法再次合并这些块。

它的时间复杂度为O(n logn)，我认为会超过时间限制。

这些算法非常有名，你可以通过谷歌搜索来获取实现细节。