`
hideto
  • 浏览: 2678933 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

CLRS笔记8,线性时间排序(counting、radix、bucket sort)

阅读更多
线性时间排序即时间复杂度为Θ(n)的排序,主要有计数排序、基数排序和桶排序
以前的排序都涉及到元素比较,称为比较排序,渐近最优的为merge sort和heap sort,时间复杂度为Θ(nlogn)
而这种排序都不是用比较的操作来排序,所以下届Θ(nlogn)对它们不适用

计数排序
1,假设数组a所有元素i满足1<=i<=k,建立数组b且初始值为0
2,读取数列每个元素,如果元素为i,则b[i]的值加一
3,遍历数组b,如果b[i]=j,就输出j次i,这样输出的序列就是已经排好序的
时间复杂度为Θ(n+k),k为常数
计数排序适合所需排序的数组元素取值范围不大的情况,如果每个元素都不一样,则效率不高
def counting_sort(a)
  min = a.min
  max = a.max
  counts = Array.new(max-min+1, 0)

  a.each do |n|
    counts[n-min] += 1
  end

  (0...counts.size).map{|i| [i+min]*counts[i]}.flatten
end


基数排序
1,假设数组a所有元素i为十进制整数且位数不超过d位
2,递归对数组a的个位、十位、...、d位排序
当没位数字都界于1到k之间时,对n个d位数的每一位处理的时间为Θ(n+k),共d次处理,所以时间复杂度为Θ(dn+dk),d为常数
基数排序分LSD(Least significant digital)和MSD(Most significant digital),前者从最低位开始排,后者从最高位开始排
LSD需要保持较低位的位置,而MSD则不需要
LSD排序图示:
数列内容:421 240 35 532 305 430 124
第1次分组
组0 240 430
组1 421
组2 532
组3
组4 124
组5 35 305
组6
组7
组8
组9
数列内容:240 430 421 532 124 35 305
第2次分组
组0 305
组1
组2 421 124
组3 430 532 35
组4 240
组5
组6
组7
组8
组9
数列内容:305 421 124 430 532 35 240
第3次分组
组0 35
组1 124
组2 240
组3 305
组4 421 430
组5 532
组6
组7
组8
组9
数列内容:35 124 240 305 421 430 532
LSD的Ruby代码实现:
def kth_digit(n, i)  # 求数字number的第kth位数字
  while(i > 1)
    n = n / 10
    i = i - 1
  end
  n % 10
end

def radix_sort(a)
  max = a.max  # 最大元素
  d = Math.log10(max).floor + 1  # 最大元素的位数

  (1..d).each do |i|
    tmp = []  # 分配10个桶
    (0..9).each do |j|
      tmp[j] = []
    end

    a.each do |n|
      kth = kth_digit(n, i)
      tmp[kth] << n  # 把元素放入桶中
    end
    a = tmp.flatten  # 把桶中元素串起来并放回原数组
  end
  return a
end


桶排序
1,假设数组a中的数字是平均分布的
2,把数组分组,放到一个个的桶中,然后对每个非空的桶排序
假设有n个数字,m个桶,平均每个桶有n/m个数字,整个算法的时间复杂度为Θ(n + m*(n/m)*log(n/m))=Θ(n+n*log(n/m)),当m接近n时复杂度接近Θ(n)
如果所有的数字都落在同一个桶中,就退化成比较排序了
def quick_sort(a)  # 快速排序
  (x=a.pop) ? quick_sort(a.select{|i| i <= x}) + [x] + quick_sort(a.select{|i| i > x}) : []
end

def first_number(n)  # 小数点后第1个数
  (n * 10).to_i
end

def bucket_sort(a)
  tmp = []  # 分配10个桶
  (0..9).each do |i|
    tmp[i] = []
  end
  
  a.each do |n|
    k = first_number(n)
    tmp[k] << n  # 把元素放入桶中
  end

  (0..9).each do |j|
    tmp[j] = quick_sort(tmp[j])  # 对每个桶快速排序
  end

  tmp.flatten
end

a = [0.75, 0.13, 0, 0.44, 0.55, 0.01, 0.98, 0.1234567]
p bucket_sort(a)

# Result: 
[0, 0.01, 0.1234567, 0.13, 0.44, 0.55, 0.75, 0.98]
分享到:
评论

相关推荐

    算法导论的习题解答和教师手册(解答)Solutions for CLRS

    这意味着对于较小规模的数据集,插入排序可能比归并排序更快,因为归并排序的对数时间复杂度在数据量较小时可能不如插入排序的线性时间复杂度来得有效。 #### 时间复杂度的比较 文档中给出了不同函数增长速度的...

    clrs-notes-solutions, 算法导论,第3版,学习笔记,习题答案.zip

    1. **基础算法**:排序(如冒泡排序、插入排序、快速排序、归并排序等)、搜索(如二分查找、广度优先搜索、深度优先搜索等)。 2. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL树和红黑树)、图...

    CLRS算法导论答案

    大名鼎鼎的 CLRS Algorithm Introduction 算法导论 课后大部分的题目解答

    CLRS(Introduction.to.Algorithms.Second.Edition)

    《CLRS:算法导论(第二版)》是计算机科学领域经典的教材,由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 和 Clifford Stein四位作者共同编写。这本书深入浅出地介绍了算法的设计、分析以及计算复杂...

    CLRS英文第二版

    CLRS英文第二版 .

    算法导论 CLRS Introduction To Algorithms chm

    算法导论 CLRS Mit Press - Introduction To Algorithms 2Nd Edition Incl Exercises Edition.chm

    clrs-mit-THIRD EDITION

    指《算法导论》(Introduction to Algorithms)。 由Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein编写,MIT出版的一本介绍、分析当代计算机...用四位作者姓的首字母组成的CLRS代表此书。

    leetcode分类-algorithm:基本算法归集,主要来源于CLRS《算法导论》,*Algo.java主要对应各个算法的实现,*Test

    根据排序算法的特性,可以分为比较排序(例如冒泡、堆排序、插入排序、归并排序、快速排序、选择排序、希尔排序等)和非比较排序(例如计数排序、基数排序和桶排序) 不同的排序,对数据类型和幅值的要求不一,因此...

    《算法导论CLRS》英文版第三版

    接着,引入了插入排序(Insertion Sort)作为简单算法的一个例子,展示了如何实现一个基本的排序算法,并对算法性能进行了分析。这部分内容是学习者掌握算法理论和实践应用的起点。 本书的第二部分着重介绍算法设计...

    CLRS算法分析教师手册

    MIT算法分析教材CLRS的教师手册,内有课程精讲及习题答案

    CLRS in C++ .zip

    C++中,`std::sort`函数提供了排序功能,而`std::lower_bound`和`std::upper_bound`则用于区间查找。 3. **动态规划**:背包问题、最短路径问题(如Floyd-Warshall算法和Dijkstra算法)、最长公共子序列、矩阵链...

    算法导论的习题解答和教师手册(手册)Instructor's Manual of CLRS

    - **第8章:线性时间排序** - 探讨几种可以在线性时间内完成排序的算法,如计数排序等。 - **第9章:中位数与序统计** - 讨论如何有效地找到一组数据的中位数或特定位置的元素。 - **第11章:哈希表** - 解释哈希表...

    CLRS Problems 15-5 Viterbi algorithm

    ### CLRS Problems 15-5 Viterbi算法解析 #### 概述 在计算机科学领域,特别是算法设计与分析方面,《Introduction to Algorithms》(通常简称为CLRS)是一本非常重要的参考书籍。本书第15章涉及动态规划,而问题...

    Instructor's Manual for CLRS(《算法导论》教师手册)

    第8章:线性时间排序 - **讲义**:介绍几种可以在线性时间内完成排序的特殊算法,如计数排序、基数排序等。 - **解答**:分析这些算法的适用条件及限制因素。 ##### 8. 第9章:中位数与顺序统计量 - **讲义**:...

    算法导论 CLRS 英文第三版

    - **ISBN**:978-0-262-03384-8 (硬皮精装版), 978-0-262-53305-8 (平装版) - **图书馆分类号**:QA76.6.I58582009 - **出版年份**:2009 #### 二、书籍结构概述 - **前言**:介绍了本书的主要特点、读者对象、...

    CLRS in C++

    algorithms from CLRS "Introduction to Algorithms 3rd" implementation in C++ templates. 《算法导论》第三版 C++泛型实现

    clrs 习题答案

    算法導論第三版习题答案

Global site tag (gtag.js) - Google Analytics