运算次数最少的排序算法

您要么要使用插入排序,要么使用基数排序。这里有一些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;
    }
}

Knuth在寻找最佳排序算法方面做了一些工作。然而,即使只有五个元素,比较次数最少的算法也是 very complicated to implement .

我建议你不要去寻找最理想的算法,而是去寻找一个易于实现和 足够满足你的需求 . 如果您可以访问标准排序算法,请首先尝试使用它。如果没有,那么可以使用插入排序或合并排序来保持简单,看看这是否对您足够好。

Insertion Sort :

• 简单的实现
• 对(相当)小的数据集有效
• 自适应,即对已经进行了实质性排序的数据集有效:时间复杂性为o(n+d),其中d是反转次数。
• 在实践中比大多数其他简单的二次型(即O(n2)算法,如选择排序或气泡排序)更有效;最佳情况(接近排序的输入)是O(n)
• 稳定,即不改变具有相同键的元素的相对顺序。
• 就地,即只需要一个恒定数量的额外内存空间O(1)
• 在线,也就是说,可以在收到列表时对其进行排序。