0

我正在尝试使用列表实现基数为 256 的基数排序。排序工作正常，但对大数组进行排序需要很长时间，此外复杂性应该是线性的，O(n)，但我没有得到那个结果，因为我正在对输出中的排序进行计时。这是我的代码：

插入功能：

//insert to the back of the list element pointed to by x
void insert(Item * ls, Item * x)
{
    x->prev = ls->prev;
    ls->prev->next=x;
    x->next=ls;
    ls->prev=x;
}

删除功能：

//delete link in list whose address is x
void delete_x(Item * x)
{
    x->prev->next = x->next;
    x->next->prev = x->prev;
    delete [] x;
}

Radix_Sort 函数：

void radix_sort_256(unsigned int *arr,unsigned int length)
//Radix sort implementation with base 256
{

    int num_of_digits=0,count=0,radix_num=0;
    unsigned int base=0,largest=0;

    Item List [256];             //Creating 256 Nodes ( Base 256 )
    for(int j=0; j<256;j++)      // Sentinel Init for each Node
    {
        List[j].key=0;
        List[j].next=&List[j];
        List[j].prev=&List[j];
    }

    for(unsigned int i=0; i<length ; i++)     //Finding the largest number in the array
    {
        if(arr[i]>largest)
            largest = arr[i];
    }

    while(largest != 0 )        //Finding the total number of digits in the bigest number( "largest" ) of the array.
    {
        num_of_digits++;
        largest = largest >> 8;
    }
    for(int i=0; i<num_of_digits; i++)
    {
        Item *node;
        for(unsigned int j=0; j<length; j++)
        {
            node = new Item;                      //Creating a new node(Total 256 nodes) and inserting numbers from the array to each node
            node->next = NULL;                    // with his own index.
            node->prev = NULL;
            node->key = arr[j];
            radix_num = ( arr[j] >> (8*i) ) & 0xFF;
            insert(&List[radix_num],node);
        }

        for(int m=0 ; m<256 ; m++)              //checking the list for keys // if key found inserting it to the array in the original order
        {
            while( List[m].next != &List[m] )
            {
                arr[count]=List[m].next->key;
                delete_x(List[m].next);             //deleting the Item after the insertion
                count++;
            }
        }
        count=0;
    }
}

主要的：

void main()
{
    Random r;
    int start,end;
    srand((unsigned)time(NULL));

    // Seting up dinamic array in growing sizes,
    //  filling the arrayes with random
    for(unsigned int i=10000 ; i <= 1280000; i*=2)
    {
        // numbers from [0 to 2147483646] calling the radix
        //  sort function and timing the results
        unsigned int *arr = new unsigned int [i];
        for(int j=0 ; j<i ; j++)
        {
            arr[j] = r.Next()-1;
        }
        start = clock();
        radix_sort_256(arr,i);
        end = clock();
        cout<<i;
        cout<<"               "<<end-start;
        if(Sort_check(arr,i))
            cout<<"\t\tArray is sorted"<<endl;
        else
            cout<<"\t\tArray not sorted"<<endl;

        delete [] arr;
    }
}

谁能看到，也许我正在做一些需要大量时间执行的不必要的操作？

4

2 回答 2

1

复杂性是一种难以掌握的野兽，因为它是多态的。

当我们谈到一个算法的复杂性时，我们一般都会把它简化，按照我们认为的瓶颈操作来表达。

例如，在评估排序算法时，复杂度表示为比较次数；但是，如果您的内存是磁带1而不是 RAM，那么真正的瓶颈是内存访问，因此快速排序 O(N log N) 最终会比冒泡排序 O(N ** 2) 慢。

在这里，您的算法可能是最佳的，它的实现似乎缺乏：例如，正在进行大量的内存分配/释放。因此，很可能是您没有正确识别瓶颈操作，并且所有关于线性复杂性的讨论都没有实际意义，因为您没有测量正确的事物。

1因为磁带从一个单元移动到另一个单元所花费的时间与这些单元之间的距离成正比，因此不断在内存中跳跃的快速排序算法最终会做很多来回操作，而冒泡排序算法只运行磁带 N 次（最大）。

于 2012-11-27T08:10:16.610 回答
0

基数为 256 的基数排序很容易看起来像这样。

void sort(int *a, int n)
{

     int i, *b, exp = 1, max = 0;
        for (i = 0; i < n; i++) {
            if (a[i] > max)
               max = a[i];
        }

      b = (int*)malloc(n * sizeof(int));
        while (max / exp > 0) {
            int box[256] = {0};
            for (i = 0; i < n; i++)
               box[a[i] / exp % 256]++;
            for (i = 1; i < 256; i++)
               box[i] += box[i - 1];
            for (i = n - 1; i >= 0; i--)
               b[--box[a[i] / exp % 256]] = a[i];
            for (i = 0; i < n; i++)
               a[i] = b[i];
            exp *= 256;
        }
   free(b);
}
于 2016-10-04T10:35:43.303 回答