排序算法1——图解冒泡排序及其实现((基于模板和函数指针的三种方法) ) ) ) ) ) ) ) ) )。
排序算法2——图简单选择排序及其实现
排序算法3——示出了直接插入排序和对折(2分钟)插入排序及其实现
排序算法4——图解希尔排序及其实现
排序算法5——图解堆积排序及其实现
排序算法633到354描绘合并排序及其递归和非递归实现
排序算法7——图解快速排序(两种主要像素选择方法)和CUTOFF时间测试
排序算法8——图表表排序
排序算法9——图解桶排序及其实现
排序算法10——图解基数排序(低位优先法LSD和高位优先法MSD ) )。
排序算法——的比较与总结
基数排序的概念基数排序是桶排序的推广。
给定n个记录，每个记录的关键字是整数，值的范围在0和m之间
当n远大于m时，将使用前面提到的桶排序。
如果m比n大很多，桶的排序需要m个桶，巨大的空间浪费
以r为基数分解关键字，r个桶就可以了。
例如：
相对于数字826
根据基数10进行分解，得到8、2、6这3个关键字，
这里，8是最上位关键字，6是最下位的关键字
根据基数16进行分解，得到3、3、a三个关键字，
这里，3是最上位关键字，a是最上位的关键字
下位优先法LSD对于给定范围在0-999之间的10个关键字{64、8、216、512、27、729、0、1、343、125}
首先为最下位的关键词制作水桶(10个)，每个最下位分别放入10个水桶
将中得到的序列按十位装入相应的桶中
进行一次采集，逐桶扫描，集中在一个链表中连接
将中得到的序列按最主位装入桶中
最后通过收集，得到有序序列
如果对n个关键字按r个时段进行基数排序，其时间复杂度为o(d(nr ) )
其中，d是收集到分配的次数，也就是关键字按照基数进行分解后的位数
如果记录的数量n和桶的数量r基本上是一个位数，则基数排序可以达到线性复杂度。
基数排序在链表中实现的好处：不需要物理移动记录，有利于大记录的排序
其代价是需要额外的o(n )空间来存储指针
测试结果和代码
1 )底层优先级法LSD #include iostream/*基数排序-底层优先级*//*元素最多有MaxDigit个关键字，基数均相同的radix */# define maxdigit4# define radix 10 结构节点{ int key； PtrToNode next； (； /*桶头节点* /结构头节点{ ptrtonode head，tail； (； typedefstructheadnodebucket [ radix ]； intgetdigit(intx，int D ) { /*默认副位D=1，主位D=MaxDigit */int d，I； for(I=1； i=D； I ) {d=X % Radix； X /=Radix； }返回d； }voidlsdraDixsort(elemtypea (，int N ) )/*基数排序-次优) */int D，di，I； Bucket B； PtrToNode tmp，p，List=NULL； for(I=0； iRadix； I(/)将每个时段初始化为空链表)/b(I ).head=b(I ).tail=null； for(I=0； iN； I ()/)将原始序列反向存储在第一个链表list(/tmp=) ptrtonode (malloc (sizeof ) structnode ) )中； tmp-key=A[i]； tmp-next=List； 列表=tmp； (/)从下排序(/for ) d=1； d=最大值； d ) (/*数据的各位循环处理(//*以下为分配的过程(*/p=List； wile(p ) ) di=获取数字(p-key，d )； /*获取当前元素的当前位数*//*从列表中获取*/tmp=p； p=p-next； /*插入B[Di]号桶尾*/tmp-next=NULL； if(b(di ).head==null ) b (di ).head=b(di ).tail=tmp； else {B[Di].tail-next=tmp； B[Di].tail=tmp； }/*接下来是收集的过程*/List=NULL； for(di=radix-1； Di=0； di--}{/*按顺序将每个桶的元素插入list */if (b [ di ].head (如果{/*桶不为空，则整个(/)桶插入Li
st表头 */B[Di].tail->next = List;List = B[Di].head;B[Di].head = B[Di].tail = NULL; /* 清空桶 */}}}/* 将List倒入A[]并释放空间 */for (i = 0; i<N; i++) {tmp = List;List = List->next;A[i] = tmp->key;free(tmp);}}template<class T>void ArrShow(T *A, int length) {for (int i = 0; i < length; ++i) {std::cout << A[i] << " ";}puts("n");}int main(int argc, char *argv[]) {int test[9] = { 1, 2, 11, 66, 53, 53, 54, 16, 4 };ArrShow(test, 9);puts("LSDRadixSort : ");LSDRadixSort(test, 9);ArrShow(test, 9);return 0;} 2）主位优先法MSD #include <iostream>/* 基数排序 - 主位优先 *//* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */#define MaxDigit 4#define Radix 10typedef int ElemType;/* 桶元素结点 */typedef struct Node *PtrToNode;struct Node{int key;PtrToNode next;};/* 桶头结点 */struct HeadNode {PtrToNode head, tail;};typedef struct HeadNode Bucket[Radix];int GetDigit(int X, int D){ /* 默认次位D=1, 主位D<=MaxDigit */int d, i;for (i = 1; i <= D; i++) {d = X%Radix;X /= Radix;}return d;}void MSD(ElemType A[], int L, int R, int D){ /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */int Di, i, j;Bucket B;PtrToNode tmp, p, List = NULL;if (D == 0) return; /* 递归终止条件 */for (i = 0; i<Radix; i++) /* 初始化每个桶为空链表 */B[i].head = B[i].tail = NULL;for (i = L; i <= R; i++) { /* 将原始序列逆序存入初始链表List */tmp = (PtrToNode)malloc(sizeof(struct Node));tmp->key = A[i];tmp->next = List;List = tmp;}/* 下面是分配的过程 */p = List;while (p) {Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 *//* 从List中摘除 */tmp = p; p = p->next;/* 插入B[Di]号桶 */if (B[Di].head == NULL) B[Di].tail = tmp;tmp->next = B[Di].head;B[Di].head = tmp;}/* 下面是收集的过程 */i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */for (Di = 0; Di<Radix; Di++) { /* 对于每个桶 */if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */p = B[Di].head;while (p) {tmp = p;p = p->next;A[j++] = tmp->key;free(tmp);}/* 递归对该桶数据排序, 位数减1 */MSD(A, i, j - 1, D - 1);i = j; /* 为下一个桶对应的A[]左端 */}}}void MSDRadixSort(ElemType A[], int N){ /* 统一接口 */MSD(A, 0, N - 1, MaxDigit);}template<class T>void ArrShow(T *A, int length) {for (int i = 0; i < length; ++i) {std::cout << A[i] << " ";}puts("n");}int main(int argc, char *argv[]) {int test[9] = { 1, 2, 11, 66, 53, 53, 54, 16, 4 };ArrShow(test, 9);puts("MSDRadixSort : ");MSDRadixSort(test, 9);ArrShow(test, 9);return 0;}