Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks
下面介绍的排序都为:非比较排序法

这里个人认为在某些特定的地方非比较排序的速度非常明显;
比如 : 对待排数据中有顺序分类,使用鸽巢总体分类,然后对不同类别的待排小数据集合采用 插入,快排等排序方式


Counting sort :计数排序
描述:迭代待排序数组出元素x,确定小于此元素[z]个数,然后把x放到它在的最终输出数组[z]上。
特性:与待排值有关;稳定的排序算法;待排序数据要求过于严格,无实际用处;
算法的步骤如下:
   1. 找出待排序的数组中最大和最小的元素
   2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项
   3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
   4. 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1


Radix sort:基数排序
描述:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
排序方式:LSD 由右向左排;MSD 由左向右排
特性:非比较排序;待排数据需要统一格式;
假设需排序数列的取值范围从1...k,我们于是建一个K+1元的数组 a[],并赋初值为0,然后便开始排序工作:
算法的步骤如下:
   1. 按输入顺序读入数列,如果所读的元素为i(1<=i<=k),我们就将a[i]的值加一,这样直到读完所有的元素。
   2. 读出元素并排序:我们遍历整个数组,如果a[i]=j(j>=0),我们就输出j次i(表示元素i在原先数列中出现了j次),这样输出的序列就是已排序的。
   3. 由于一般排序算法涉及到元素之间的比较,如果化成比较树可以知道,这样的排序算法复杂度的下限是O(N*lnN),而计数排序没有比较元素,所以所需排序时间就少了,我们可以看到计数排序的复杂度为O(n*k),其中k(k的定义同上)为合并排列所需的时间,是个常数。
   4. 此算法适合所需排列的元素取值范围不大的情况下,否则会造成空间的消耗,比如,一共100个元素,其取值范围从1-100000,显然这个时候用基数排序是不合适的。



Bucket sort:桶排序
描述:工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。
桶排序以下列程序进行:
   1. 设置一个定量的阵列当作空桶子。
   2. 寻访序列,并且把项目一个一个放到对应的桶子去。
   3. 对每个不是空的桶子进行排序。
   4. 从不是空的桶子里把项目再放回原来的序列中。



Pigeonhole sort:鸽巢排序
描述:是一种时间复杂度为O(n)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法. 但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用.
算法的步骤如下:与桶排同





整理 www.blogjava.net/Good-Game
posted on 2009-12-08 14:21 刘凯毅 阅读(1594) 评论(1)  编辑  收藏 所属分类: 算法/函数

Feedback

# re: 跟我一起学 - 算法导论 - 线性时间排序 2009-12-11 16:30 av
收藏le~  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: