运算次数最少的排序算法是什么?我需要在 HLSL 中实现它作为 WPF 的像素着色器效果 v2.0 的一部分,因此考虑到像素着色器的限制,它需要进行非常少量的操作。我需要对 9 个值进行排序,特别是当前像素及其邻居。
问问题
1950 次
2 回答
4
您要么想使用插入排序,要么使用基数排序。以下是一些 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;
}
}
于 2010-06-11T20:05:31.363 回答
2
Knuth 在寻找最佳排序算法方面做了一些工作。然而,即使只有五个元素,具有最少比较次数的算法实现起来也非常复杂。
我建议不要试图找到最佳算法,而应尝试找到一种易于实现且足以满足您的需求的算法。如果您可以访问标准排序算法,请先尝试使用该算法。如果不是,那么您可以使用插入排序或合并排序来保持简单,看看这对您来说是否足够好。
插入排序:
- 简单的实现
- 对(相当)小数据集有效
- 自适应,即对已经基本排序的数据集有效:时间复杂度为 O(n + d),其中 d 是反转次数
- 在实践中比大多数其他简单的二次算法更有效,即 O(n2) 算法,如选择排序或冒泡排序;最好的情况(接近排序的输入)是 O(n)
- 稳定,即不改变具有相同键的元素的相对顺序
- 就地,即只需要固定数量的 O(1) 额外内存空间
- 在线,即可以在收到列表时对其进行排序。
于 2010-06-11T19:27:28.920 回答