Nim 编程实现快速排序
2019-08-29 本文已影响0人
Python高效编程
快速排序是一种平均时间复杂度为 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编程。