排序算法----基数排序(RadixSort(L,max))单…
2018-06-18 04:10:45来源:未知 阅读 ()
转载http://blog.csdn.net/Shayabean_/article/details/44885917博客
先说说基数排序的思想:
基数排序是非比较型的排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。
将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。在每一次排序中,按照当前位把数组元素放到对应
的桶当中,然后把桶0到桶9中的元素按先进先出的方式放回数组中。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
这个版本的基数排序RadixSort(L,max)较RadixSort(L)不同的是需要输入待排序列最大数的位数。因为RadixSort(L)最大数位在程序中已经计算过了,因为需要计算最大数,所以需要对待排链表最开始循环一次,所以RadixSort(L,max)速度比RadixSort(L)稍快。
这篇博客包括4个文件,两个头文件RadixSort.h和fatal.h,一个库函数RadixSort.c,和一个测试文件Test_Radix_Sort.c
头文件fatal.h:
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define Error(Str) FatalError(Str) 4 #define FatalError(Str) fprintf(stderr, "%s\n", Str), exit(1);
头文件RadixSort.h:
1 typedef int ElementType; 2 #ifndef RADIX_SORT_H 3 #define RADIX_SORT_H 4 5 #include<stdbool.h> 6 #define ListEmpty -2 7 8 struct Node; 9 typedef struct Node *PtrToNode; 10 typedef PtrToNode List; 11 typedef PtrToNode Position; 12 13 List MakeEmpty(List L); 14 bool IsEmpty(List L); 15 bool IsLast(Position P, List L); 16 Position Header(List L); 17 Position Advance(Position P); 18 ElementType Retrieve(Position P); 19 void DeleteList(List L); 20 void PrintList(const List L); 21 void Insert(ElementType X, List L, Position P); 22 void MoveNode(List L1, List L2);//将表L2中的头节点移动成为L1的尾节点 23 void RadixSort(List L,int max);//最终基数排序函数,输入链表L,将L排序得到新的排序链表L,其中max是待排元素最高有多少位 24 #endif // !RADIX_SORT_H
其中RadixSort是最终排序函数,调用它即可排序。
库函数RadixSort.c
1 #include "RadixSort.h" 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<malloc.h> 5 #include<math.h> 6 #include"fatal.h" 7 struct Node 8 { 9 ElementType Element; 10 Position Next; 11 }; 12 13 //初始化链表 14 List MakeEmpty(List L) 15 { 16 if (L != NULL) 17 DeleteList(L);//如果链表非空,则删除链表 18 L = malloc(sizeof(struct Node)); 19 if (L == NULL) 20 FatalError("Out of memory!"); 21 L->Next = NULL; 22 return L; 23 } 24 //判断链表是否为空 25 bool IsEmpty(List L) 26 { 27 return L->Next == NULL; 28 } 29 30 //判断当前指针P是否指向链表最后一个元素 31 bool IsLast(Position P, List L) 32 { 33 return P->Next == NULL; 34 } 35 36 //获取链表头 37 Position Header(List L) 38 { 39 return L; 40 } 41 42 //获取位置P的下一个位置 43 Position Advance(Position P) 44 { 45 return P->Next; 46 } 47 48 //提取位置P处结构里面的值 49 ElementType Retrieve(Position P) 50 { 51 return P->Element; 52 } 53 54 //删除链表 55 void DeleteList(List L) 56 { 57 Position P, Temp; 58 P = L->Next; 59 L->Next = NULL; 60 while (P != NULL) 61 { 62 Temp = P->Next; 63 free(P); 64 P = Temp; 65 } 66 } 67 68 //打印链表 69 void PrintList(const List L) 70 { 71 Position P = Header(L); 72 if (IsEmpty(L)) 73 printf("Empty list\n"); 74 else 75 { 76 do 77 { 78 P = Advance(P); 79 printf("%d ", Retrieve(P)); 80 } while (!IsLast(P, L)); 81 printf("\n"); 82 } 83 } 84 85 //插入元素X到位置P后面 86 void Insert(ElementType X, List L, Position P) 87 { 88 Position TmpCell; 89 TmpCell = malloc(sizeof(struct Node)); 90 if (TmpCell == NULL) 91 FatalError("Out of Space!!!"); 92 TmpCell->Element = X; 93 TmpCell->Next = P->Next; 94 P->Next = TmpCell; 95 } 96 97 void MoveNode(List L1, List L2) 98 { 99 //将表L2中的头节点移动成为L1的尾节点 100 Position Tmp1 = L1; 101 Position Tmp2; 102 if (IsEmpty(L2)) exit(ListEmpty); 103 while (!IsLast(Tmp1,L1)) 104 Tmp1 = Tmp1->Next;//使Tmp1指向L1表尾 105 Tmp2 = L2->Next; 106 L2->Next = Tmp2->Next; 107 Tmp1->Next = Tmp2; 108 Tmp2->Next = NULL; 109 } 110 111 void RadixSort(List L,int max) 112 { 113 //if (IsEmpty(L)) return L; //如果要排序的链表L是空表,则不排序 114 int i,j, TmpSub;//Tmpsub存储数的个位、十位、百位 115 ElementType FirstElement;//存储链表的第一个元素 116 117 List Bucket[10];//开辟10个桶,依次为0~9 118 for (i = 0; i < 10; i++) Bucket[i] = MakeEmpty(NULL);//对10桶进行初始化,每一个数组都是一个链表 119 for (i = 0; i < max; i++)//开始提取每一位数的个位、十位、百位 120 { 121 while (!IsEmpty(L))//当L中的元素被取光了,则循环结束 122 { 123 FirstElement = L->Next->Element;//取出第一个节点的数据 124 TmpSub = (int)(FirstElement / pow(10, i)) % 10;//依次取出个十百位数字 125 MoveNode(Bucket[TmpSub], L);//将L中的节点依次移到对应的桶中 126 } 127 for (j = 0; j < 10; j++) //将桶中的数再次移动到L中 128 { 129 while (!IsEmpty(Bucket[j])) MoveNode(L, Bucket[j]); 130 } 131 } 132 for (i = 0; i < 10; i++) free(Bucket[i]) ;//释放掉10个桶 133 }
测试函数Test_Radix_Sort.c
1 #include<stdio.h> 2 #include "RadixSort.h" 3 #include"fatal.h" 4 #include<time.h> 5 6 int main() 7 { 8 int amount;
10 List L; Position P; 11 L = MakeEmpty(NULL);//初始化链表 12 P = L; 13 if (L == NULL) Error("Out of Space!!!"); 14 printf("随机生成多少位数:"); 15 scanf_s("%d", &amount); 16 srand((unsigned)time(NULL)); 17 for (int i = 0; i < amount; i++) 18 { 19 Insert(rand() % 10000, L, P); 20 P = Advance(P); 21 } 22 printf("排序前的结果:"); 23 PrintList(L); 24 RadixSort(L,4);//调用排序函数排序 25 printf("基数排序后的结果:"); 26 PrintList(L); 27 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:关于fefo函数
- C++ rand函数 2020-06-10
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash