c - 短数组的最佳排序函数

Question

我正在研究一种处理图片的算法。 基本上我会实现扩散(每个像素将获得周围 8 个像素的中值 + 它自己的值)。

我要做的是创建一个包含值的 9 个整数的数组，对数组进行排序并在数组 [4] 处获取中值。

我仍然不知道该用什么来解决这个问题，对于相对较小的数组，最好的排序函数是什么？排序函数将大致调用 x 次，x 是像素数。

Heapsort 似乎有点矫枉过正。快速排序不会表现得那么好。而且我不想实现非常复杂的事情。

大家怎么看？

Answer 1

如果您只需要中位数，则根本不需要进行任何排序! (对于长数组，请参阅 http://en.wikipedia.org/wiki/Selection_algorithm 的 O(n) 算法；当然我们这里只讨论短数组)。

对于 9 个数字的中位数，稍微谷歌一下就会显示文章 Fast median search: an ANSI C implementation N. Devillard 的文章，它指向 J. L. Smith 的文章在 XC4000E FPGA 中实现中值滤波器，它提供了这种不言自明的“排序网络”以使用 19 次比较获得中值:

在 C 方面:

typedef int T;

void sort2(T* a, T* b);
void sort3(T* a, T* b, T* c);
T min3(T a, T b, T c);
T max3(T a, T b, T c);

T median9(T p1, T p2, T p3, T p4, T p5, T p6, T p7, T p8, T p9)
{
    sort3(&p1, &p2, &p3);
    sort3(&p4, &p5, &p6);
    sort3(&p7, &p8, &p9);

    p7 = max3(p1, p4, p7);
    p3 = min3(p3, p6, p9);

    sort3(&p2, &p5, &p8);
    sort3(&p3, &p5, &p7);

    return p5;
}

void sort2(T* a, T* b)
{
    if (*a > *b)
    {
        T tmp = *b;
        *b = *a;
        *a = tmp;
    }
}

void sort3(T* a, T* b, T* c)
{
    sort2(b, c);
    sort2(a, b);
    sort2(b, c);
}

T min3(T a, T b, T c)
{
    if (a < b)
        return a < c ? a : c;
    else
        return b < c ? b : c;
}

T max3(T a, T b, T c)
{
    if (a > b)
        return a > c ? a : c;
    else
        return b > c ? b : c;
}

---

编辑:this file还包含获取 3、5、6、7、9 和 25 个数的中位数的代码。

#define PIX_SORT(a,b) { if ((a)>(b)) PIX_SWAP((a),(b)); }
#define PIX_SWAP(a,b) { pixelvalue temp=(a);(a)=(b);(b)=temp; }

/*----------------------------------------------------------------------------
   Function :   opt_med9()
   In       :   pointer to an array of 9 pixelvalues
   Out      :   a pixelvalue
   Job      :   optimized search of the median of 9 pixelvalues
   Notice   :   in theory, cannot go faster without assumptions on the
                signal.
                Formula from:
                XILINX XCELL magazine, vol. 23 by John L. Smith

                The input array is modified in the process
                The result array is guaranteed to contain the median
                value
                in middle position, but other elements are NOT sorted.
 ---------------------------------------------------------------------------*/

pixelvalue opt_med9(pixelvalue * p)
{
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ;
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ;
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ;
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ;
    PIX_SORT(p[4], p[2]) ; return(p[4]) ;
}