一、基数排序

（从小到大的）基数排序的主要思想就是我们先将我们所有的数据按照个位进行排序，然后按照十位进行排序，再依次按照高位进行排序，最后得到我们排序的从小到大的结果。

Radix Sort

这里我们简单举一个例子，将我们的45,12,67,42三个数排序

45 12 67 42

首先我们按照个位进行排序。注意我们这里每一列所代表的都是以同一个数为结尾的数据。第一列所代表的就是以1结尾的，第二列所代表的就是以2结尾的，第三列所代表的就是以三为结尾的，以此类推。

也就是说我们可以通过一个队列数组来满足我们的需要。

42
12 45 67

然后我们将我们的数据重新写回去。

12 42 45 67

然后我们以此类推，按照十位进行排序

45
12 42 67

然后我们再将数据写回去

12 42 45 67

这时，我们就发现我们的数据已经变成有序的了。

1.代码实现

以下的代码我们是写在我们的头文件里面的声明(sort.h)

typedef int ElemType;
//基数排序
void RadixSort(int *a ,int n);
//求最大值
int wheremax(int *a ,int n);
//求出排序的关键字
int getKey(int value,int k);
//分发函数
void Distribute(int *a,int left,int right,int k);
//回收数据
void collect(int *a);

以下的代码我们写在我们的 sort.c文件里面

//创建一个有十个元素的数组，数组中的每一个元素都是队列。
//关于队列和排序的完整代码会在下面给出
Queue que[10]={0};
//这里我们需要创建一个函数来求出我们当前排序的所有数据中的最大的数。
ElemType wheremax(int *a ,int n)
{
    int max=a[0];
    for(int i=0;imax)
        {
            max=a[i];
        }
    }
    return max;
}

//这里取得我们排序的关键字，value表示我们传入的数据
//k表示我们需要取出的是我们数据从右往左的第几位。
int getKey(ElemType value,int k)
{
    int key=0;
//取出我们从右往左第k位。
    key=(value%(int)(pow(10,k))-value%(int)(pow(10,(k-1))))/pow(10,(k-1));
    return key;
}

//分发函数，这里我们需要将我们的数据按照我们的从右往左第k位，分别送入对应的队列当中。
void Distribute(int *a,int left,int right,int k)
{
    for(int i=left;i 
 
  以下的代码写在我们的测试文件中test.c 
 
const int num=400;

int main() 
{
//这里我们随机生成400个数进行测试实验。
    int b[400];
    for (int i =0;i 
 
 第一行是我们排序前的数据，第二行是我们排序完成之后的数据 
 
 
2.代码汇总  
 
 test.c已经在上面完整地放出，下面我们仅将队列文件呈现。 
 有关队列的内容请参考博文队列的实现（c语言数据结构）_桜キャンドル淵的博客-CSDN博客 
 下面的代码写在queue.c文件中  
 
#include "queue.h"

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }

    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    assert(newnode);

    newnode->data = x;
    newnode->next = NULL;

    if (pq->tail == NULL)
    {
        assert(pq->head == NULL);
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head && pq->tail);

    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);

    //return pq->head == NULL && pq->tail == NULL;
    return pq->head == NULL;
}

size_t QueueSize(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    size_t size = 0;
    while (cur)
    {
        size++;
        cur = cur->next;
    }

    return size;
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->tail);

    return pq->tail->data;
}
 
 
 下面的代码写在queue.h文件中  
 
#ifndef QUEUE_QUEUE_H
#define QUEUE_QUEUE_H

#include 
#include 
#include 
#include 
#include "queue.h"
typedef int QDataType;

typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;

    //size_t size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);


#endif //QUEUE_QUEUE_H 
 
 在生成完了我们上述的queue.c与queue.h文件之后我们只需要在我们的sort.h文件中包含一下我们的queue.h头文件就可以运行了。 
 
 二、冒泡排序 
 
 冒泡排序的核心思想就是将我们的数据前后两两比较，如果要实现从小到大排序的话，就将大的换到后面。每一趟排序完成后，都有一个数下沉到最后的位置。以此类推，最终完成我们的排序。 
 

 
 Bubble sort
 
  
typedef int ElemType;
//交换函数
void Swap(ElemType *a,ElemType *b)
{
    ElemType temp=*a;
    *a=*b;
    *b=temp;
}

//定义冒泡排序的主函数，下面的代码为升序的冒泡排序的写法
void BubbleSort(ElemType *a,int n)
{
    assert(a);
    for(int j=0;ja[i])
            {
                Swap(&a[i-1],&a[i]);
                exchange=1;
            }
        }
//没有发生交换，我们的数据已经有序
        if(exchange==0)
        {
            return;
        }
    }
}

基数排序+冒泡排序【c语言数据结构】

C/C++/C#相关栏目本月热门文章