盒子
盒子
文章目录
  1. Nim 每日早茶

Nim 编程实现快速排序

Nim 每日早茶

Nim 编程实现快速排序

https://tea.nim-cn.com/archives/

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

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

预处理
随机产生分位点

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

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

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

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import random


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


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

为了简单测试我们的递归版快速排序的性能,我们可以使用命令 nimble install timeit 安装简易性能测试模块。

1
2
3
4
5
6
7
8
9
10
11
12
when isMainModule:
import algorithm, sequtils, timeit

let size = 100
var a0 = newSeqWith(size, rand(100))
var a1 = a0
timeonce("sort"):
sort(a0)
assert a0 != a1
timeOnce("quick sort"):
quicksort(a1)
echo a0 == a1

我们可以改变 size 的数值,来测试性能,使用 --d:release 编译执行文件。

size = 100

输出:

1
2
3
sort -> [27μs 500.00ns]
quick sort -> [6μs 300.00ns]
true

size = 1000

输出:

1
2
3
sort -> [136μs 100.00ns]
quick sort -> [91μs 200.00ns]
true

size = 10000

输出:

1
2
3
sort -> [1ms 72μs 800.00ns]
quick sort -> [1ms 193μs 100.00ns]
true

size = 100000

输出:

1
2
3
sort -> [12ms 351μs 200.00ns]
quick sort -> [69ms 355μs 300.00ns]
true

显然当 size 大于 100000 的时候,我们的玩具算法就出现了瓶颈。

所以说,当标准库能够满足我们的需求的时候,如果不是为了学习的目的,轻易不要自己造轮子。