【CLRS】《算法导论》读书笔记(三):计数排序(Counting sort)、基数排序(Radix sort)和桶排序(Bucket sort)

时间:2020-12-14 17:09:02

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