操作次数最少的排序算法

Question

操作次数最少的排序算法是什么？我需要在 HLSL 中实现它作为 WPF 的像素着色器效果 v2.0 的一部分，因此考虑到 Pixel Shader 的局限性，它需要的操作数量非常少。我需要对 9 个值进行排序，特别是当前像素及其邻居。

Answer 1

您想要使用插入排序或基数排序。以下是一些 C++ 实现：

基数排序

void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ )
    count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for ( i=1; i<256; i++ )
    index[i]=index[i-1]+count[i-1];
  for ( i=0; i<N; i++ )
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

您需要调用radix()四次，因为它只适用于一列。

插入排序

void insertSort(int a[], int length)
{    
    int i, j, value;
    for(i = 1; i < length; i++)
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
            a[j + 1] = a[j];
        a[j + 1] = value;
    }
}