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

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

计数排序（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

最差时间复杂度: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

平均时间复杂度：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

发表评论

表情：
评论列表 （有 0 条评论，304人围观）

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

相关阅读

    相关 计数排序(Counting-Sort)

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

    ゝ一纸荒年。ゝ一纸荒年。/ 0 赞/ 225 阅读