Nim 编程实现快速排序

快速排序是一种平均时间复杂度为 nlog(n) 的原地排序，很适合大规模数据排序。它采用一种分而治之的手段，划分子问题，并递归地求解问题，最后将子问题的解合并为原问题的解。

快速排序的思想：在待排序列表中寻找一个分位点，处理列表，使得分位点左边是小于分位点处元素的子列表，而分位点右面是大于分位点元素的子列表。然后在子列表中选取分位点，重复上述操作，直到列表为单元素列表，合并子列表即可得到有序列表。

预处理
随机产生分位点

将分位点处的元素与首元素交换

交换
使变量 i “指向” 第二个元素，而变量 j “指向” 末尾元素。向右移动变量 i（i ++)，直到变量 i “指向” 一个大于分位点的数值。这时向左移动变量 j (j --)，直到变量j “指向” 一个小于分位点的元素。如果这时 i < j，那么就交换 i, j所在位置的元素。如果 i > j，跳出循环，并交换 j 和首地址所在位置的元素。

到这时，我们已经成功找到一个分位点。分位点左面的元素都小于等于分位点元素，分位点右面的元素都大于等于分位点元素。我们然后继续在左右部分各自寻找新的分位点。

最终代码

### 微信公众号：nim编程
import random


# 交换元素
proc swap(list: var seq[int], i: int, j: int) =
  let temp = list[i]
  list[i] = list[j]
  list[j] = temp 


proc qsort(list: var seq[int], lo: int, hi: int) =
    # 基准条件
    if lo >= hi:
      return 
    # 选取分位点
    let pivot = rand(lo..hi)
    var i = lo + 1
    var j = hi
    swap(list, lo, pivot)
    var running = true
    while running:
      while list[i] < list[lo] and i < hi:
        i += 1
      while list[j] > list[lo] and j > lo:
        j -= 1
      if i < j:
        swap(list, i, j)
      else:
        running = false
    swap(list, lo, j)
    # 递归求解子问题
    qsort(list, lo, j - 1)
    qsort(list, j + 1, hi)




proc quicksort(list: var seq[int]) = 
  qsort(list, 0, list.len - 1)

运行结果：

### 微信公众号：nim编程
var s = @[1, 4, 2, 9, 13, 5, 3, 19]
echo s
==> @[1, 4, 2, 9, 13, 5, 3, 19]
quicksort(s)
echo s
==> @[1, 2, 3, 4, 5, 9, 13, 19]
关注微信公众号：nim编程。