有没有一种简单的方法来对char*数组进行排序？C++

Question

我在一个文件中有一个char*数组。我所在的公司将数据存储在平面文件中。有时数据是排序过的，但有时并不是。我想对文件中的数据进行排序。

现在我可以从头开始编写代码来完成这个任务。是否有更简单的方法?

当然，原地排序可能是最好的选择。我正在处理大型文件，并且内存很小。但我会考虑所有选项。

所有字符串长度相同。

这是一些示例数据:

the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt

这将代表三个长度为28的记录。应用程序知道长度。每个记录以CRLF (\r\n)结尾，但对于此排序来说并不重要。

- baash05

---

你是在谈论可以读入内存的短文本文件，还是有数百万行文本的巨大文件？如果可以将它们读入内存，那么这很简单，但对于规模更大的东西，需要采用不同的方法。 - Simon Howard

我希望它能够处理大文件。这是为了PDA而设计的，有时候内存不是那么方便（哈哈...方便~PDA哈！） - baash05

Answer 1

template<size_t length> int less(const char* left, const char* right) {
    return memcmp(left, right, length) < 0;
}

std::sort(array, array + array_length, less<buffer_length>);

- Leon Timmermans

---

std::sort期望参数为迭代器。它可以处理像向量这样的东西，但我怀疑它能够处理数组。 - Mehrdad Afshari

需要验证的是我们可以声明char array[10000][28+1]，然后读入数据。或者可能声明array[1][28+1]，分配正确数量的行，然后读入数据。不过，这种方法非常脆弱。GNU sort更好。 - user3458

将其分成几部分，然后在这些部分上进行“排序合并”。 - Leon Timmermans

请注意，这仅适用于在编译时已知长度的情况。 - Johannes Schaub - litb

那么如果我在编译时不知道长度呢？我正在面临这个问题。我不知道记录的长度在编译时是多少。我使用了qsort解决了这个问题，但我需要更好的性能。http://stackoverflow.com/questions/11484856/sorting-a-buffer-using-stl-sort - p.magalhaes

Answer 2

如果无法将数据装入内存，请使用GNU sort程序（外部程序）：它可以对任意大小的文件进行排序，而且文件越大，创建进程的额外成本就越小。

- Aaron Digulla

Answer 3

您可以在原生数据类型的数组上使用STL中的算法，而不仅仅是在STL容器上使用。然而，使用std::sort的另一个建议不能按照发布的方式工作，因为strcmp返回一个值，当字符串不相同时，该值对所有比较求值为true，而不仅仅是左侧小于右侧--这是std::sort想要的;一个二进制谓词返回左侧小于右侧为真。

以下代码可行：

struct string_lt : public std::binary_function<bool, char, char>
{
    bool operator()(const char* lhs, const char* rhs)
    {
        int ret = strcmp(lhs, rhs);
        return ret < 0;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    char* strings [] = {"Hello", "World", "Alpha", "Beta", "Omega"};
    size_t numStrings = sizeof(strings)/sizeof(strings[0]);

    std::sort(&strings[0], &strings[numStrings], string_lt());

    return 0;
}

- John Dibling

Answer 4

boost::bind 可以实现这个功能：

// ascending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) < 0); 

// descending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) > 0); 

编辑：这些字符串没有以null结尾：

// ascending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) < 0); 

// descending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) > 0); 

- litb

Answer 5

如果文件很大，无法适应内存，则可以使用bin/bucket排序将数据拆分成较小的文件，最后将这些片段聚合到一个结果文件中。其他响应将向您展示如何对每个单独的桶文件进行排序。

- Ovidiu Pacurar

Answer 6

可能最简单的方法是使用旧的stdlib.h函数qsort。 这应该可以工作：

qsort( array, num_elements, sizeof( char* ), strcmp )

请注意，这是标准的C语言，只能可靠地处理英文文本。

如果您有一组字符串对象，则在C++中还有其他可能性。

如果您正在Linux上编写gtk或Qt应用程序，则建议您事先查看这些库。

- Ralf

---

与Mehrdad的答案一样，这是错误的答案。qsort将传递'const char **'（双指针）的const void指针转换，并且strcmp（）不喜欢那个--有充分的理由。 - Jonathan Leffler

Answer 7

有几件事情需要考虑：

1. 如果您的数据太大而无法放入内存，您可能希望仅在内存中建立文件偏移量的索引，然后内存映射文件以访问字符串（取决于您的操作系统）。
2. 原地排序将需要大量的内存复制。如果可以的话，请使用希尔排序。然后，一旦您知道最终顺序，重新排序字符串就更容易了，可以在线性时间内完成。
3. 如果字符串都是相同长度的，则确实需要基数排序。如果您不熟悉基数排序，这里是基本思想：基于比较的排序（这就是std :: sort，qsort和任何其他通用排序所做的）总是需要O（N log N）时间。 基数排序逐个比较单个数字（从str [0]开始，以str [K-1]结束，其中K为长度），总体上只需要O（N）时间来执行。

请参考互联网获取比我更详细的基数排序算法描述。除了我提到的内容，我建议避免使用所有其他使用标准库排序工具的解决方案。很遗憾，它们并不适合你的特定问题。

- tbarta

Answer 8

你可能需要研究一下内存映射文件（参见http://en.wikipedia.org/wiki/Memory-mapped_file），以及在POSIX兼容的操作系统上使用mmap()函数（http://en.wikipedia.org/wiki/Mmap）。这样，你就可以获得一个指向表示文件内容的连续内存的指针。

好处是操作系统会负责将文件的部分加载到内存中，并在需要时卸载它们。

缺点之一是，如果有多个进程可能访问该文件，则需要采用某种形式的文件锁定来避免损坏。

另一个缺点是，这并不能保证良好的性能 - 要做到这一点，你需要一个排序算法，试图避免不断地加载和卸载页面（除非当然你有足够的内存将整个文件加载到内存中）。

希望这给你一些想法！

- unwesen

Answer 9

在C语言中，对字符数组进行排序的规范方法是使用间接级别来调用strcmp()函数。虽然这种方法也可以在C++中使用，但并不一定推荐。

static int qsort_strcmp(const void *v1, const void *v2)
{
    const char *s1 = *(char * const *)v1;
    const char *s2 = *(char * const *)v2;
    return(strcmp(s1, s2));
}

static void somefunc(void)   // Or omit the parameter altogether in C++
{
    char **array = ...assignment...
    size_t num_in_array = ...number of char pointers in array...
    ...
    qsort(array, num_in_array, sizeof(char *), qsort_strcmp);
    ...more code...
}

- Jonathan Leffler