知识卡片
计数排序用键范围换比较
计数排序用整数键作为计数数组下标,先统计各值出现次数,再由这些次数确定结果位置,避免靠两两比较决定相对顺序。输入本身或提取的键必须适合这种有限整数索引模型。
它的时间O(n+k)同时依赖元素数n和键范围k,不是无条件比O(n log n)比较排序更快。若最大键很大而只有少数元素,计数数组可能占用太多空间;常把k=O(n)等范围条件成立时称线性排序。
本章实现要求0≤data[j],k为最大值加1;仅说“整数”还不够,负数不能直接用作此数组下标。空输入/大小溢出等边界也不能由该接口自动解决。
216⁄02967 int ctsort(int* data,int size,int k),成功0、分配失败-1,结果覆盖原数组。k控制计数数组范围,不是元素个数;所有键需合法索引,调用者还要保证size/k及分配大小合法。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 计数排序用键范围换比较
- · 计数排序的接口定义
原书出处 · 2 处
- · 查看原书依据
计数排序的描述 计数排序是一种高效的线性排序,它通过计算一个集合中元素出现的次数来确定集合如何排列。不同于之前介绍的一些算法是基于比较的,计数排序不需要进行元素比较,而且它的运行效率要比效率为O(nlg n)比较排序高。 计数排序有一定的局限性。其中最大的局限就是它只能用于整型或者那些可以用整型来表
- · 查看原书依据
k为data中最大的整数加1。当ctsort返回时,data中包含已排序的元素。 复杂度 O(n+k),n为要排序的元素的个数,k为data中最大的整数加1。
参考来源
- 位置:《算法精解:C语言描述》第12章《计数排序的描述》(spine1347;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1313.html;u215-ch12-014)。
- 结论依据:215完整频次数组/整型局限段及216 O(n+k)接口、217实际counts[data[j]]实读,范围约束是代码直接前提,不添加负数偏移实现。
- 原始内容:计数排序的描述 计数排序是一种高效的线性排序,它通过计算一个集合中元素出现的次数来确定集合如何排列。不同于之前介绍的一些算法是基于比较的,计数排序不需要进行元素比较,而且它的运行效率要比效率为O(nlg n)比较排序高。 计数排序有一定的局限性。其中最大的局限就是它只能用于整型或者那些可以用整型来表
- 位置:《算法精解:C语言描述》第12章《计数排序的接口定义》(spine1348;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1314.html;u216-ch12-014)。
- 结论依据:216/02967 int ctsort(int* data,int size,int k),成功0、分配失败-1,结果覆盖原数组。k控制计数数组范围,不是元素个数;所有键需合法索引,调用者还要保证size/k及分配大小合法。
- 原始内容:k为data中最大的整数加1。当ctsort返回时,data中包含已排序的元素。 复杂度 O(n+k),n为要排序的元素的个数,k为data中最大的整数加1。