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

Question

我正在为嵌入式系统开发软件,我需要实现一个排序例程,而我在选择最佳解决方案时遇到了麻烦.我的要求如下:

1. 因为这是一个非常受内存限制的系统,所以空间复杂性是一个主要因素.
2. 因为要排序的元素的数量通常很小,并且排序仅偶尔发生,所以时间复杂度不一定是主要因素.
3. 稳定的算法是我的应用程序的要求.
4. 因为这是一个嵌入式系统,所以代码大小是一个因素.
5. 无法保证数据最初的排序几乎是按顺序排列的.

我考虑过以下算法:

• 泡泡排序(是的,即使我很惭愧地说出来)
• 侏儒排序
• 插入排序
• 就地合并排序(虽然在我看来,链接列表比数组更理想？)

虽然答案(对于我的确切情况)可能很好,"呃,呃,这并不重要,对我们所关心的所有人使用冒泡排序",这个答案并不是很有用.通常,哪种排序算法对嵌入式系统有用？

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

我怀疑由于缺少函数调用,使用小数据集的更快的气泡排序是如此.

从中可以看出,对于较小的数据集,算法的效率通常并不重要,因为像big-O这样的东西通常与数据集变大时相关.

但是,此测试是在我的环境中完成的,您的测试可能会有很大差异.我建议在您的环境中执行相同的测量 - 实现冒泡排序,只考虑在必要时转移到更复杂的算法.

在评论者的建议下,我重新运行测试,srand(42)然后rand()填充数组元素.在这种情况下,对于冒泡排序,结果仅稍微差一点,对于10,000个元素,642与413毫秒相比,对于1,000个元素,结果为82对74毫秒.

考虑到问题中的约束(小元素数,不常排序,稳定性要求,低空间复杂度),我仍然更喜欢将冒泡排序简单化为任何更复杂的算法.

不过,请记住我之前的建议:你需要在自己的环境中计时.结果可能大不相同.您可以使用我提供的代码作为执行此操作的基准.说真的,如果你选择的方法花费的时间少于一秒,那么它对你的目的来说可能已经足够了.