知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.13 · 生成模型:未记录

计数排序用键范围换比较

理解等级:中级

计数排序用整数键作为计数数组下标,先统计各值出现次数,再由这些次数确定结果位置,避免靠两两比较决定相对顺序。输入本身或提取的键必须适合这种有限整数索引模型。

它的时间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。