盒子
盒子
文章目录
  1. Nim编程入门
    1. 线性排序

Nim 语言实现计数排序

Nim编程入门

我们常见的归并排序、快速排序的平均时间复杂度都为 Olog(N),这一节我们介绍一种线性排序 — 计数排序,在限定的条件下,可以以 O(N) 的时间复杂度完成排序。

线性排序

线性排序,适用于序列中最大值较小的整数序列。

首先,我们求出序列中最大值 max,创建辅助序列 aidaid 序列的大小为 0 .. max

第一步,我们循环待排序序列 x,增加 aid[x[i]] 的数值。换句话说,我们通过 aid 的索引指代序列的元素,aid 的值指代该元素出现了多少次。比如 x = @[1, 4, 1, 6, 7],则 aid = @[0, 2, 0, 0, 1, 0, 1, 1]x[0] = 1, 那么 aid[1] += 1

第二步,我们让 aid[i] = aid[i-1],注意为保证下标从零开始,我们需要将 aid[0] 减一。此时 aid 的含义是,对于当前下标 i 来说,有多少个元素小于等于 iaid = @[0, 2, 0, 0, 1, 0, 1, 1],现在 aid = @[-1, 1, 1, 1, 2, 2, 3, 4]

第三步,我们从 aid 序列恢复排序的结果。每个元素放在对应的下标上,我们把遇到的重复元素放在靠前的位置。因为我们是从序列的尾部向前循环,所以实现的计数排序是稳定排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
proc countingSort*[T](x: seq[T]): seq[T] =
let
length = x.len
smax = max(x)
var aid = newSeq[T](smax + 1)
result = newSeq[T](length)
for i in 0 ..< length:
aid[x[i]] += 1

aid[0] -= 1
for i in 1 .. smax:
aid[i] += aid[i-1]

for i in countdown(x.high, 0, 1):
result[aid[x[i]]] = x[i]
aid[x[i]] -= 1


when isMainModule:
var x = @[2, 5, 3, 0, 2, 3, 0, 3]
echo countingSort(x)

输出

1
@[0, 0, 2, 2, 3, 3, 3, 5]