Nim 编程实现希尔排序

Nim中文教程

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

主程序

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

# 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 来判断数组是否已经有序。

when isMainModule:
  import random, sequtils, algorithm


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

输出

true