什么是适合嵌入式系统的排序算法？

Question

我正在为嵌入式系统开发软件，我需要实现一个排序例程，而且我在选择最优解决方案时遇到了困难。我的要求如下：

1. 因为这是一个内存非常有限的系统，空间复杂性是一个主要因素。
2. 由于要排序的元素的数量通常很小，而且排序只偶尔发生，所以时间复杂性不一定是一个主要因素。
3. 一个稳定的算法是我的应用程序的一个要求。
4. 因为这是一个嵌入式系统，代码大小是一个因素。
5. 没有人能保证数据最初将是一个几乎排序的顺序。

我考虑了以下算法：

• 泡泡类(是的，尽管我不好意思这么说)
• gnome排序
• 插入排序
• 就地合并排序(虽然在我看来，使用链接列表比数组更理想？)

虽然答案(对我的确切情况)很可能是，“嗯，这真的不重要，用泡泡排序作为我们所有关心的”，这个答案并不是很有用。一般来说，什么样的算法在嵌入式系统中是有用的？

Answer 1

插入排序也是好的，它在实践中运行快，稳定和到位.它与gnome排序有很大关系，在实践中速度更快，但是对于gnome排序，代码更小一些，它占用的辅助空间更少(不是大O，区别在于常量)。

编辑:是的，我搞砸了，倒过来了--我可能不该在喝咖啡之前回答问题。它以前说过插入排序比gnome排序有更少的代码和空间。

Answer 2

不要为泡沫感到羞耻，它有它的位置。如果您的数据集很小，那么编写代码就容易了，如果您做得对，就会很稳定(永远不要交换相同的元素)。

如果您的数据大部分是按每一次传递的交替方向排序的，那么它的速度也会令人目眩。我知道你说过它一开始不是很接近分类，我是说如果你排序的话，它会变成这样的可能性。在这两种情况下，如果数据集的大小很小，那么如果数据集完全没有排序，那就不重要了。

如果您在对另一个答案的评论中提到，数据集的大小大约为11，那么情况尤其如此。如果没有明确设计成故意可怕的排序算法，那么任何算法都可以很容易地处理这样的大小。

如果您的环境没有提供一个稳定的类型，那么考虑到您的约束和属性，我只会选择泡泡类型。

实际上，使用下面的程序和time实用程序，我发现用于qsort和冒泡排序的CPU时间只有在元素计数达到10,000时才开始起作用。

即使如此，泡泡的时间还不到半秒钟。除非你每秒钟要做很多事情，否则这就无关紧要了。

#include <stdio.h>
#include <stdlib.h>

static int data[10000];
#define SZDATA (sizeof (*data))
#define NMDATA (sizeof (data) / sizeof (*data))

int compfn (const void *a, const void *b) {
    if (*((int*)a) > *((int*)b))
        return 1;
    if (*((int*)a) < *((int*)b))
        return -1;
    return 0;
}

int main (void) {
    int i, tmp, swapped, count;

    for (i = 0; i < NMDATA; i++)
        data[i] = (i * 3) % 11;

    if (0) {
        qsort (data, NMDATA, SZDATA, compfn);
    } else {
        swapped = 1;
        count = NMDATA;
        while (swapped) {
            swapped = 0;
            for (i = 1; i < count; i++) {
                if (data[i] < data[i-1]) {
                    tmp = data[i];
                    data[i] = data[i-1];
                    data[i-1] = tmp;
                    swapped = 1;
                }
            }
            count --;
        }
    }

    //for (i = 0; i < NMDATA; i++)
        //printf ("%10d\n", data[i]);

    return 0;
}

通过改变data数组和if (0)语句的大小，我得到了以下结果(以毫秒为单位)，每种情况下运行五次：

Data size | qsort | bubble
----------+-------+-------
      100 |    61 |     76
          |    76 |     76
          |    77 |     61
          |    61 |     60
          |    61 |     61  avg qsort = 67, bubble = 67

     1000 |    77 |     93
          |    61 |     45
          |    76 |     77
          |    77 |     76
          |    76 |     77  avg qsort = 73, bubble = 74
          |       |
    10000 |    92 |    414
          |    77 |    413
          |    61 |    413
          |    76 |    405
          |    61 |    421  avg qsort = 73, bubble = 413

我怀疑用较小的数据集进行更快的气泡排序是因为缺少函数调用。

从这一点来看，对于较小的数据集，算法的效率通常并不重要，因为当数据集变得更大时，像大-O这样的东西通常是相关的。

然而，这个测试是在我的环境中完成的，而您的测试可能会有很大的不同。我建议在您的环境中执行相同的度量--实现气泡排序，并且只有在必要时才考虑采用更复杂的算法。

根据评论者的建议，我使用srand(42)和rand()重新运行测试，以填充数组元素。在这种情况下，气泡排序的结果仅略差一些，10,000个元素为642毫秒，413毫秒，1,000元素为82和74毫秒。

考虑到问题中的约束(小元素计数、不频繁排序、稳定性要求、低空间复杂度)，与任何更复杂的算法相比，我仍然更喜欢气泡排序的简单性。

不过，请记住我先前的建议:您需要在自己的环境中计时。结果可能大不相同。您可以使用我提供的代码作为进行此操作的基线。说真的，如果你选择的任何方法少于一秒钟，它可能就足以满足你的目的。

Answer 3

一个系统是否嵌入并不重要。重要的是您列出的因素:代码大小约束、可用内存、所需速度和元素数量。

按照您所描述的，气泡排序是一个完全可以接受的解决方案:它小、可预测、易于内存，并且非常容易实现和调试。我在上世纪80年代初看到了一个证据，即泡泡排序是n≤11的最佳时间。现代的快捷键可能会稍微改变这一点，但我怀疑这样的盈亏可能会减少很多。

若要使不稳定排序算法稳定，请添加包含原始位置的排序键。只有当主键是领带时，才引用辅助键。