基数排序:类似于桶排序,划分关键字,关键字为元素下标,进行多次入“桶”完成排序

特点

将每个元素划分出多个关键字(元素的每一位数),将依次关键字作为下标来存放元素后按照下标依次排出每个元素,重复多次,直到关键字使用完毕,如果使用二维数组实现会容易出现内存浪费的情况,因此在C语言实现中我定义了一个链表节点的结构,实现了链表,用于减少内存浪费,当然在C++中可以直接使用vector,虽然效率低一点但是编写起来比较容易

总的来说基数排序适合对元素位数相近的数组进行排序

在这里我处理了数组中含有正整数和负整数的情况,并且在C语言实现中inA被更改,C语言实现直接原地排序,这里可以对int型数据进行排序,如果需要对浮点数排序,需要做特殊处理,使其符合关键字-值对应的关系

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过但超时(效率低
TJsort_1

注意:该实现会修改原数组,并且是返回有序的原数组

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    struct Node
    {
        int dat;
        struct Node* next;
    };
    struct Node* KeyT[20];
    memset(KeyT, 0, 20 * sizeof(struct Node*));

    size_t Key = 1;
    while (true)
    {
        for (size_t i = 0; i < numsSize; i++)
        {
            if (nums[i] >= 0)
            {
                struct Node** p = &KeyT[(nums[i] / Key) % 10];
                while (*p != 0)
                {
                    p = &(*p)->next;
                }
                *p = (struct Node*)calloc(1, sizeof(struct Node));
                (*p)->dat = nums[i];
                (*p)->next = 0;
            }
            else
            {
                struct Node** p = &KeyT[(nums[i] / (int)Key) % 10 + 19];

                while (*p != 0)
                {
                    p = &(*p)->next;
                }
                (*p) = (struct Node*)calloc(1, sizeof(struct Node));
                (*p)->dat = nums[i];
                (*p)->next = 0;
            }
        }

        size_t SetX = 0;
        for (size_t i = 10; i < 20; i++)
        {
            struct Node* p = KeyT[i];
            while (p)
            {
                struct Node* delp = p;
                nums[SetX] = p->dat;
                SetX++;
                p = p->next;
                free(delp);
            }
        }

        for (size_t i = 0; i < 10; i++)
        {
            struct Node* p = KeyT[i];
            while (p)
            {
                struct Node* delp = p;
                nums[SetX] = p->dat;
                SetX++;        

                p = p->next;
                free(delp);
            }
            if (SetX >= numsSize)
            {
                if (i == 0)
                {
                    return nums;                    
                }
                
            }
        }

        memset(KeyT, 0, 20 * sizeof(struct Node*));
        Key *= 10;
    }

    return 0;
}

C++实现

Leetcode上917.排序数组中测试通过(效率还行
TJsort_2

vector<int> sortArray(vector<int>& nums)
{
    vector<int> Vect[20];
    vector<int> outA = nums;
    size_t Key = 1;
    size_t Len = outA.size();
    while (Key <= 1000000000)
    {
        for (size_t i = 0; i < Len; i++)
        {
            if (outA[i] >= 0)
            {
                Vect[outA[i] / Key % 10].push_back(outA[i]);
            }
            else
            {
                Vect[outA[i] / (int)Key % 10 + 19].push_back(outA[i]);
            }
        }

        size_t SetX = 0;
        for (size_t i = 10; i < 20; i++)
        {
            for (size_t j = 0; j < Vect[i].size(); j++)
            {
                outA[SetX] = Vect[i][j];
                SetX++;
            }
            Vect[i].clear();
        }

        for (size_t i = 0; i < 10; i++)
        {
            for (size_t j = 0; j < Vect[i].size(); j++)
            {
                outA[SetX] = Vect[i][j];
                SetX++;
            }
            Vect[i].clear();
        }

        Key *= 10;
    }
    
    return outA;
}
Last modification:April 15th, 2020 at 09:12 am