盒子
盒子
文章目录
  1. Nim中文教程
    1. 主程序
    2. 测试程序

Nim 编程实现希尔排序

Nim中文教程

这一节,我们使用 Nim 语言实现希尔排序。希尔排序是插入排序的改良版。

主程序

希尔排序的主要思想,是使得任意间隔为 size 的元素都是有序的。在我们的示例中,size 是 3 的倍数。size 每次变为原来三分之一,我们使用插入排序,使得数组中间隔为 size 的元素都是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# three
proc shellSort*[T](x: var openArray[T]) =
let length = len(x)
var size = 1
while size < length:
size *= 3 + 1
while size >= 1:
for i in size ..< length:
let temp = x[i]
for j in countdown(i, size, size):
if x[j - size] > temp:
x[j] = x[j - size]
else:
x[j] = temp
break
size = size div 3

测试程序

我们使用 algorithm 模块中的 isSorted 来判断数组是否已经有序。

1
2
3
4
5
6
7
8
when isMainModule:
import random, sequtils, algorithm


randomize()
var x = newSeqWith(1000, rand(0 .. 100000000))
shellSort(x)
echo isSorted(x)

输出

1
true