详解基数排序

1.基数排序

基数排序是一种特殊的排序方式，不是基于比较进行排序，而是基于关键字的各个位置大小进行"分配"和"收集"两种操作对关键字序列进行排序的一种排序方式。

基数排序可以分为：最高位优先（MSD）和最低位优先（LSD）

2.基数排序原理

1.观察排序字段最大的数字，它有几位决定了需要分配和收集的次数

2.按照元素每一位的大小分配入对应容器（如数组，链表，队列等）

3.按照容器的次序依次收集数据

4.重复前两步，直至每一位都分配，收集完毕

例如：

3.代码实现

本算法使用链表作为分配存储数据的容器

//基数排序
void radixSort(int arr[],int length) {

    LinkList list[10];  
    //找出最大值，计算排序的次数
    int initMax = arr[0];  //记录数组首元素，并找出数组中最大的元素
     
    int loop = true;
    int count=1;  //用来记录需要几趟将元素放入对应链表中

    //找出序列中最大的元素
    for (int i = 1; i < length; i++) {
        if (arr[i] > initMax) {
            initMax = arr[i];
        }
    }
    //计算需要几趟将元素放入对应链表中
    while (loop) {
        initMax = initMax / 10;
        if (initMax) {
            count++;
        }
        else {
            loop = false;
        }
    }

    for (int i = 0; i < 10; i++) {
        //开辟10个链表，带头结点
        list[i]=(LinkList)malloc(sizeof(Node));
        list[i]->next = NULL;
        list[i]->size = 0;  //初始化每个链表的大小
    }

    for (int i = 0; i < count; i++) {
        //将元素放入对应的链表
        for (int j = 0; j < length; j++) {
            int refer = (int)(arr[j] / pow(10, i)) % 10;  //要放进链表的下标
            Node* s = (Node*)malloc(sizeof(Node));
            if (!s) {
                printf("分配内存失败");
            }
            Node* p = list[refer];   //指向插入第refer个链表
            while (p->next) {      //找到最后一个结点，方便再最后的位置进行增加元素
                p = p->next;
            }
            s->data = arr[j];
            s->next = p->next;
            p->next = s;
            list[refer]->size++;
        }
        //收集数据
        int pos=0;  //记录要放回元素的位置
        for (int i = 0;i<10;i++) {
            Node* p = list[i]->next;   // 用来查找下一节点
            Node* temp;//用来释放找完的结点，方便下一次将元素装入链表不出错
            if (p) {
                for (int j = pos; j < pos + list[i]->size; j++) {
                    temp = list[i]->next;   //记录释放的结点
                    arr[j] = p->data;  
                    p = p->next;
                    list[i]->next = p;
                    free(temp);   //释放结点，防止下次收集出错

                }
                pos = list[i]->size + pos;
                list[i]->size = 0;
            }
        }
        
    }
}