随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 177758
  • 排名 - 147

最新评论

阅读排行榜

评论排行榜

建议先看看前言 : http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

这一节讲的是非线性排序。

一.计数排序(Counting Sort)

基本思想:对每一个输入元素x,确定出小于x的元素个数。

适用范围:适用于输入是由小范围的整数构成的序列。

稳定性:算法是稳定的。

具体实现:

 1 /*
 2 Author: Tanky Woo
 3 Blog:   www.WuTianQi.com
 4 Description: 计数排序
 5 */
 6 #include <iostream>
 7 using namespace std;
 8  
 9 // arr--初始输入数组, res--存放排序结果的数组,hash临时存储区[0k]
10 int arr[100], res[100], hash[100];
11 int len, k = -1;
12  
13 void PrintHash()
14 {
15     cout << "Hash数组: " << endl;
16     for(int i=0; i<=k; ++i)
17         cout << hash[i] << " ";
18     cout << endl;
19 }
20  
21 void countingSort()
22 {
23     for(int i=0; i<=k; ++i)
24         hash[i] = 0;
25     // 此过程记录每一个元素的个数
26     for(int i=1; i<=len; ++i)
27         ++hash[arr[i]];
28     PrintHash();
29     // 此过程确定小于x的元素的个数
30     for(int i=1; i<=k; ++i)
31         hash[i] += hash[i-1];
32     PrintHash();
33     // 思考这里为何从i=len开始?而不从i=1开始?
34     for(int i=len; i>0--i)
35     {
36         res[hash[arr[i]]] = arr[i];
37         --hash[arr[i]];
38     }
39 }
40 /*
41 思考这里为何从i=len开始?而不从i=1开始?
42 保持排序后结果的稳定性!
43 因为同一个元素,靠后的元素在排序后相对也是从后开始存入结果数组的。
44 */
45  
46 int main()
47 {
48     cout << "输入元素个数: ";
49     cin >> len;
50     cout << "输入" << len << "个元素: " << endl;
51     for(int i=1; i<=len; ++i)
52     {
53         cin >> arr[i];
54         if(k < arr[i])
55             k = arr[i];
56     }
57     countingSort();
58     cout << "排序后结果为: " << endl;
59     for(int i=1; i<=len; ++i)
60         cout << res[i] << " ";
61     cout << endl;
62 }

输出结果:

jishupaixu


二.基数排序(Radix Sort)

基本思想:按组成关键字的各个位的值来实现排序的。

排序方式:

排序方式:LSD 由右向左排; MSD 由左向右排

稳定性:算法是稳定的。

推荐:严蔚敏《数据结构》上的基数排序。

先说下什么是基数:计算的基数就是基本的单元数。比如10进制的基数就是10,二进制的基数就2,八进制的基数是8等等。

基数排序说通俗点,就是把带排序的N个数字右对齐排成一列。然后把相同的位数互相比较,来排序。

例图:

jishu

以下是具体实现和分析:

 1/*
 2Author: Tanky Woo
 3Blog:   www.WuTianQi.com
 4Description: 基数排序
 5*/

 6#include <iostream>
 7#include <cstring>
 8using namespace std;
 9 
10int arr[100], res[100], hash[10];
11int n;
12 
13int maxbit()
14{
15       int _max = 0;
16       int temp[100];
17       for(int i=0; i<n; ++i)
18           temp[i] = arr[i];
19 
20       for (int i=0; i<n; ++i)
21       {
22              int tt = 1;
23              while(temp[i]/10 > 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 
35void radixSort()
36{
37    memset(res, 0sizeof(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<n; ++j)
47        {
48            tmp = (arr[j]/radix)%10;
49            ++hash[tmp];
50        }

51        for(int j=1; j<10++j)
52            hash[j] += hash[j-1];
53        for(int j=n-1; 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; ++j)
60            arr[j] = res[j];
61        radix *= 10;
62    }

63}

64 
65int main()
66{
67    freopen("input.txt""r", stdin);
68    cout << "输入元素个数: ";
69    cin >> n;
70    cout << "输入" << n << "个元素: " << endl;
71    for(int i=0; i<n; ++i)
72        cin >> arr[i];
73    radixSort();
74    cout << "排序后结果为: " << endl;
75    for(int i=0; i<n; ++i)
76        cout << res[i] << " ";
77    cout << endl;
78}

推荐一个基数排序的动画演示:http://blogimg.chinaunix.net/blog/upfile/070912120349.swf

桶排序就不写了,本质就是计数排序和基数排序的结合。
不过我有点不明白,我们一般说的桶排序貌似就是基数排序?

在我独立博客上的原文:http://www.wutianqi.com/?p=2378

欢迎大家互相学习,互相探讨。

posted on 2011-04-24 09:28 Tanky Woo 阅读(1508) 评论(4)  编辑 收藏 引用

FeedBack:
# re: 《算法导论》学习总结 — 8.第八章(2) 计数排序 && 基数排序 && 桶排序 2011-04-29 21:43 KingJ
今天刚看了这一章,感觉书上对基数排序的内容写的有点朦胧,来看lz写的感觉比较直观,桶排序看着一堆公式感觉好乱  回复  更多评论
  
# re: 《算法导论》学习总结 — 8.第八章(2) 计数排序 && 基数排序 && 桶排序 2011-04-29 21:48 Tanky Woo
@KingJ
呵呵,怎么说呢,书上的分析还是很给力的,我能做的也就是补充一些,然后实现,大家共勉吧。至于那个堆排序,我也不太明白,他的给力之处到底在哪。。。而且在我印象中基数排序又称堆排序的。  回复  更多评论
  
# re: 《算法导论》学习总结 — 8.第八章(2) 计数排序 && 基数排序 && 桶排序 2011-04-29 22:06 KingJ
@Tanky Woo
我感觉书上的分析理解了以后能有种豁然开朗的感觉,呵呵,方便留个qq吗
?交流交流,呵呵  回复  更多评论
  
# re: 《算法导论》学习总结 — 8.第八章(2) 计数排序 && 基数排序 && 桶排序 2011-04-30 11:59 Tanky Woo
@KingJ
给你发私信了~~~  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理