算法导论,《算法导论》学习总结 — 8.第八章(2) 计数排序 && 基数排序 && 桶排序

on 2011-4-24 in 博文摘选 | 0 Comment
建议先看看前言 ： http://www.cnblogs.com/tanky_woo/archive/2011/04/09/2010263.html
这一节讲的是非线性排序。
一.计数排序(Counting Sort)
基本思想：对每一个输入元素x，确定出小于x的元素个数。
适用范围：适用于输入是由小范围的整数构成的序列。
稳定性：算法是稳定的。
具体实现：
/*
Author: Tanky Woo Blog: www.WuTianQi.com Description: 计数排序 */ #include using namespace std; // arr--初始输入数组， res--存放排序结果的数组，hash临时存储区[0...k] int arr[100], res[100], hash[100]; int len, k = -1; void PrintHash() { cout << "Hash数组: " << endl; for(int i=0; i<=k; ++i) cout << hash[i] << " "; cout << endl; } void countingSort() { for(int i=0; i<=k; ++i) hash[i] = 0; // 此过程记录每一个元素的个数 for(int i=1; i<=len; ++i) ++hash[arr[i]]; PrintHash(); // 此过程确定小于x的元素的个数 for(int i=1; i<=k; ++i) hash[i] += hash[i-1]; PrintHash(); // 思考这里为何从i=len开始？而不从i=1开始？ for(int i=len; i>0; --i) { res[hash[arr[i]]] = arr[i]; --hash[arr[i]]; } } /* 思考这里为何从i=len开始？而不从i=1开始？ 保持排序后结果的稳定性！ 因为同一个元素，靠后的元素在排序后相对也是从后开始存入结果数组的。 */ int main() { cout << "输入元素个数: "; cin >> len; cout << "输入" << len << "个元素: " << endl; for(int i=1; i<=len; ++i) { cin >> arr[i]; if(k < arr[i]) k = arr[i]; } countingSort(); cout << "排序后结果为: " << endl; for(int i=1; i<=len; ++i) cout << res[i] << " "; cout << endl; }
输出结果：
jishupaixu算法导论,《算法导论》学习总结 — 8.第八章(2) 计数排序 &amp;&amp; 基数排序 &amp;&amp; 桶排序
二.基数排序(Radix Sort)
基本思想：按组成关键字的各个位的值来实现排序的。
排序方式：
排序方式：LSD 由右向左排; MSD 由左向右排
稳定性：算法是稳定的。
推荐：严蔚敏《数据结构》上的基数排序。
先说下什么是基数：计算的基数就是基本的单元数。比如10进制的基数就是10，二进制的基数就2，八进制的基数是8等等。
基数排序说通俗点，就是把带排序的N个数字右对齐排成一列。然后把相同的位数互相比较，来排序。
例图：
jishujishupaixu算法导论,《算法导论》学习总结 — 8.第八章(2) 计数排序 &amp;&amp; 基数排序 &amp;&amp; 桶排序
以下是具体实现和分析：
1 /*
2 Author: Tanky Woo 3 Blog: www.WuTianQi.com 4 Description: 基数排序 5 */ 6 #include 7 #include 8 using namespace std; 9 10 int arr[100], res[100], hash[10]; 11 int n; 12 13 int maxbit() 14 { 15 int _max = 0; 16 int temp[100]; 17 for(int i=0; i 0) 24 { 25 tt++; 26 temp[i] /= 10; 27 } 28 if(_max < tt) 29 _max = tt; 30 } 31 cout << "_max : " << _max << endl; 32 return _max; 33 } 34 35 void radixSort() 36 { 37 memset(res, 0, sizeof(res)); 38 int nbit = maxbit(); 39 int tmp; 40 int radix = 1; 41 // 以下和计数排序一样 42 for(int i=1; i<=nbit; ++i) 43 { 44 for(int j=0; j<10; ++j) 45 hash[j] = 0; 46 for(int j=0; j=0; --j) 54 { 55 tmp = (arr[j]/radix)%10; 56 --hash[tmp]; 57 res[hash[tmp]] = arr[j]; 58 } 59 for(int j=0; j> n; 70 cout << "输入" << n << "个元素: " << endl; 71 for(int i=0; i> arr[i]; 73 radixSort(); 74 cout << "排序后结果为: " << endl; 75 for(int i=0; i推荐一个基数排序的动画演示：http://blogimg.chinaunix.net/blog/upfile/070912120349.swf
桶排序就不写了，本质就是计数排序和基数排序的结合。
不过我有点不明白，我们一般说的桶排序貌似就是基数排序？
在我独立博客上的原文：http://www.wutianqi.com/?p=2378
欢迎大家互相学习，互相探讨。
Tags:  算法导论中文版 算法导论答案 算法导论pdf 基数排序 算法导论

延伸阅读

最新评论

发表评论