建议先看看前言 : http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
这一节讲的是非线性排序。
一.计数排序(Counting Sort)
基本思想:对每一个输入元素x,确定出小于x的元素个数。
适用范围:适用于输入是由小范围的整数构成的序列。
稳定性:算法是稳定的。
具体实现:
输出结果:
二.基数排序(Radix Sort)
基本思想:按组成关键字的各个位的值来实现排序的。
排序方式:
排序方式:LSD 由右向左排; MSD 由左向右排
推荐:严蔚敏《数据结构》上的基数排序。
先说下什么是基数:计算的基数就是基本的单元数。比如10进制的基数就是10,二进制的基数就2,八进制的基数是8等等。
基数排序说通俗点,就是把带排序的N个数字右对齐排成一列。然后把相同的位数互相比较,来排序。
例图:
以下是具体实现和分析:
推荐一个基数排序的动画演示:http://blogimg.chinaunix.net/blog/upfile/070912120349.swf 桶排序就不写了,本质就是计数排序和基数排序的结合。不过我有点不明白,我们一般说的桶排序貌似就是基数排序?
在我独立博客上的原文:http://www.wutianqi.com/?p=2378
欢迎大家互相学习,互相探讨。