【CLRS】《算法导论》读书笔记（三）：计数排序（Counting sort）、基数排序（Radix sort）和桶排序（Bucket sort）...

た入场券 2022-01-09 10:23 171阅读 0赞

**计数排序（Counting sort）**

维基百科：[http://en.wikipedia.org/wiki/Counting\_sort][http_en.wikipedia.org_wiki_Counting_sort]

时间复杂度：O(n)

技术排序的基本思想：对每一个输入元素 x ，确定小于 x 的元素个数。利用这一信息，就可以直接把 x 放到它在输出数组中的位置上了。

伪码：

COUNTING-SORT（A, B, k）

let C\[0 .. k\] be a new array

for i = 0 to k

C\[i\] = 0

for j = 1 to A.length

C\[A\[j\]\] = C\[A\[j\]\] + 1

// C\[i\] now contains the number of elements equal to i.

for i = 1 to k

C\[i\] = C\[i\] + C\[i - 1\]

// C\[i\] now contains the number of elements less than or equal to i.

for j = A. length downto 1

B\[C\[A\[j\]\]\] = A\[j\]

C\[A\[j\]\] = C\[A\[j\]\] - 1

**基数排序（Radix sort）**

维基百科：[http://en.wikipedia.org/wiki/Radix\_sort][http_en.wikipedia.org_wiki_Radix_sort]

最差时间复杂度:O(k n)，其中k为位数

基数排序分类：LSD（Least Significant Digital）和MSD（Most Signifacant Digital）

LSD伪码：

RADIX-SORT(A, d)

for i = 1 to d

use a stable sort to sort array A on digit i

**桶排序（Bucket sort）**

维基百科：[http://en.wikipedia.org/wiki/Bucket\_sort][http_en.wikipedia.org_wiki_Bucket_sort]

平均时间复杂度：O(n)

Bucket sort works as follows:

1.  Set up an array of initially empty "buckets."
2.  **Scatter**: Go over the original array, putting each object in its bucket.
3.  Sort each non-empty bucket.
4.  **Gather**: Visit the buckets in order and put all elements back into the original array.

伪码：

BUCKET-SORT(A)

n = A.length

let B\[0 .. n - 1\] be a new array

for i = 0 to n - 1

make B\[i\] an empty list

for i = 1 to n

insert A\[i\] into list B\[nA\[i\]\]

for i = 0 to n -1

sort list B\[i\] with insertion sort

concatenate the list B\[0\], B\[1\], ..., B\[n -1\] together in order

转载于:https://www.cnblogs.com/dyingbleed/archive/2013/03/14/2956558.html

[http_en.wikipedia.org_wiki_Counting_sort]: http://en.wikipedia.org/wiki/Counting_sort
[http_en.wikipedia.org_wiki_Radix_sort]: http://en.wikipedia.org/wiki/Radix_sort
[http_en.wikipedia.org_wiki_Bucket_sort]: http://en.wikipedia.org/wiki/Bucket_sort

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关基数排序(Radix Sort)----(排序算法十四)

1.排序原理 2.代码实现 include <stdio.h> include <malloc.h> define RA

我就是我/ 2022年09月17日 15:13/ 0 赞/ 122 阅读

相关桶排序(Bucket Sort)----(排序算法七)

1.算法原理将元素的值放入另一数组下标与其相等的位置排序前： 6 2 4 1 5 9 桶中：bucket\[10\]= 0 1 2 0 4 5 6 0 0

傷城~/ 2022年09月17日 14:16/ 0 赞/ 95 阅读

相关计数排序(Counting-Sort)

计数排序的思想是在一个预排序的整数集中，统计每一个整数在这个整数集中小于等于本身的整数个数，这样的话，就得到了预排序整数集中每个数的在已排序集中的位置，然后将预排序集与预排

ゝ一纸荒年。/ 2022年05月16日 11:20/ 0 赞/ 105 阅读

相关排序算法：桶排序、计数排序、基数排序

相关博客： [排序算法：冒泡排序、插入排序、选择排序、希尔排序][Link 1] [排序算法：归并排序、快速排序][Link 2] [排序算法：桶排序、计数排序、基

左手的ㄟ右手/ 2022年04月23日 08:38/ 0 赞/ 301 阅读

相关【CLRS】《算法导论》读书笔记（三）：计数排序（Counting sort）、基数排序（Radix sort）和桶排序（Bucket sort）...

计数排序（Counting sort）维基百科：[http://en.wikipedia.org/wiki/Counting\_sort][http_en.wikipedi

た入场券/ 2022年01月09日 10:23/ 0 赞/ 172 阅读

相关深入解析基数排序（Radix sort）——线性时间排序算法

简介众所周知，常见的排序算法例如快速排序，归并排序等都是基于比较的排序算法。正是因为它们基于比较的特性，这些算法在时间复杂度方面无法做到比`O(nlogn)`更好。关于

缺乏、安全感/ 2021年12月19日 01:57/ 0 赞/ 183 阅读

相关《算法导论》——计数排序Counting Sort

　　今天贴出的算法是计数排序Counting Sort。在经过一番挣扎之前，我很纠结，今天这个算法在一些scenarios，并不是最优的算法。最坏情况和最好情况下，时间复杂度差

不念不忘少年蓝@/ 2021年12月09日 01:11/ 0 赞/ 172 阅读

相关 Java 基数排序（Radix Sort）

文章目录 * 算法描述动图演示代码实现算法分析基数排序也是非比较的排序算法，对每一位进行排序，从最...

你的名字/ 2020年06月14日 03:10/ 0 赞/ 782 阅读

相关 Java 桶排序（Bucket Sort）

文章目录 * 算法描述图片演示代码实现算法分析桶排序是计数排序的升级版。它利用了函数的映射关系，高...

你的名字/ 2020年06月14日 03:08/ 0 赞/ 713 阅读

相关 Java 计数排序（Counting Sort）

文章目录 * 算法描述动图演示代码实现算法分析计数排序的核心在于将输入的数据值转化为键存储在额外开...

你的名字/ 2020年06月14日 02:57/ 0 赞/ 740 阅读