当前位置：文江博客话题详情

操作次数最少的排序算法

发布于 2024-09-05 20:58:22 字数 125 浏览 7 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

﹎☆浅夏丿初晴 2024-09-12 20:58:22

您想要使用插入排序或基数排序。以下是一些 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;
    }
}

You either want to use Insertion sort or Radix sort. Here are some C++ implementations:

Radix Sort

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];
}

You need to call radix() four times, as it only works on one column.

Insertion Sort

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;
    }
}

回复收藏 0 原文

等风来 2024-09-12 20:58:22

Knuth 在寻找最佳排序算法方面做了一些工作。然而，即使只有五个元素，比较次数最少的算法也是实施起来非常复杂。

我建议您不要试图找到最佳算法，而是尝试找到一种易于实现且足以满足您的需求的算法。如果您可以使用标准排序算法，请首先尝试使用该算法。如果没有，那么您可以使用插入排序或合并排序来保持简单，看看这对您来说是否足够好。

插入排序：

简单的实现
对于（相当）小的数据集非常有效
自适应，即对于已经基本排序的数据集有效：时间复杂度为 O(n + d)，其中 d 是反转次数
在实践中比大多数其他简单二次（即 O(n2)）算法（例如选择排序或冒泡排序）更高效；最好的情况（接近排序的输入）是 O(n)
稳定，即不会改变具有相等键的元素的相对顺序
就地，即仅需要恒定数量的 O(1) 额外内存空间
在线，即可以在收到列表时对列表进行排序。