输入文件的计数排序

Question

我的计数排序要处理一个用数字填充的数组。现在我想制作它，所以我从输入文件中获取信息。我会有大量数字（从0到4000）的输入文件。我还将得到该文件中的项目数。我将如何调整此代码以适用于任何输入文件？

    int array[10]={5,5,5,5,5,5,1,2,5,7};
    int count_array[10]={0};
    int sum=0;
    int new_array[10];
    int i;
    for(i=0;i<10;i++)
        count_array[array[i]]++;
    for(i=0;i<10;i++)
    {
        count_array[i]=count_array[i]+sum;
        sum=count_array[i];
    }
    for(i=0;i<10;i++)
    {
        new_array[count_array[array[i]]]=array[i];
        count_array[array[i]]--;
    }
    for(i=1;i<=10;i++)
    {
        cout<<new_array[i]<<" ";               
    }
    cout<<endl;

Answer 1

如果您处理的是整数，并且您确信您的情况下的范围是0-4000。

然后，您可以安全地忽略计数排序，并做一些类似于计数频率的事情，最终会对文件中的整数进行排序。

请参阅以下代码，对constant space(4001*siz4eof(int))和theta(N)时间中的输入进行排序

#include <fstream>
#include <iostream>
#include <string>
#include <cstring>
#include <cassert>
#define MAX_VALUE 4001
int main()
{
    std::ifstream in("D:\cprog\file.txt");
    std::string line;
    int arr[MAX_VALUE];
    memset(arr,0,sizeof(arr));
    while(std::getline(in,line))
    {
        int a = std::stoi(line);
        assert(a<MAX_VALUE);
        arr[a] += 1; // counting frequency of a number
    }
    std::cout<<"Sorted result"<<'n';
    for(int i = 0; i < MAX_VALUE ; ++i)
    {
        for(int j = 0 ; j < arr[i] ; ++j)
            std::cout<<i<<'n';
    }
    return 0;
}

计数排序是一个stable sorting technique，它为像Redix排序算法这样的排序算法提供了基础。

对于纯整数，几乎不要求稳定性。所以你们可以选择上面的技术来快速排序你们的输入。