【在厨房想30天的演算法】Day 15 演算法 : 排序 sort II 堆积、合并、快速

Aloha!又是我少女人妻终於来到第 15 天了~不知不觉就过了一半了,大家有听过跑者愉悦理论吗,就是很多事情再坚持一下,突破撞墙期後会突然有满满能量涌现,所以凡事都要告诉自己再坚持一下下,那种厌烦与疲惫的感受很快就会消散的!阿不过我通常累了就去睡觉了哈哈哈哈哈哈!


常见的排序演算法

昨天提到了气泡排序、选择排序以及插入排序,今天要继续提及其他的排序法搂~

堆积排序 Heap Sort

堆积排序是利用堆积树的性质来做排序,堆积资料结构请参考文章:资料结构:堆积 Heap 中的说明。

一开始先将数列储存在堆积中
wCYBq2b

从根节点取出元素
ck0HGo1
lLjSwkI

重新调整堆积,再从根节点取出元素
Xhh2is7
Yqw74rD

再重新调整堆积,再从根节点取出元素
AA8Lh96
r23JoNM

一直反覆操作直到所有元素都排列完成~
iVOs8rv

合并排序 Merge Sort

合并排序是将数列分割为左右两个几乎等长的数列,之後再分割,直到不可分割为止,再依序比对并合并。

将未排序数列尽量分为两组 (如黄色底线所示)
daNvSKk

划分後的数列再进行划分 (如粉色底线所示)
HqQdDT1

这时元素 5 跟 3 还能再进行划分 (如蓝色底线所示)
721jhMb

无法再划分後开始将元素合并,先从最左方、最下层开始合并,合并时比较两元素的大小,并做排序。
X7VRVeQ

较小的数排前方,此时 3 < 5 ,所以 3 排在前方
IQlDs9L

再比较左方两数列的第一个数,此时是 1 < 3
dF9vMvx

所以先取 1 排前方,再取 3 ,最後取 5
YHICPit

再将 2 、 4 依照上述方式比较後合并,最後得到两数列
wxsojiA

再比较两数列第一个值,因 1 < 2 ,所以 1 先排入 1 ,其次为 2
1wB2X6e

同理比较 3 跟 4,并做合并,最後排入 5
ryuBslG
bmWs5P9

当啷~然後排序就完成了~
wGgAtuT

快速排序

快速排序是从数列中随机选择一个基准值,将小於基准的数排在基准值的左边,大於基准值的数在右边,被基准值分割的两数列再用上述的方式重复执行并排序,直到排序完成为止。

取一组未排序的元素数列,并随机取一个元素当基准点,下图选择 3 为基准点
Li8l94L

将小於基准值的元素排左边,大於基准值的元素排右边
WTa1Qw4

因 5 > 3 ,所以 5 排在 3 的右边
cQnzwRF

因 1 < 3 ,所以 1 排在 3 的左边
cura2TS
ZLA0c7z

同理,2 排在 3 的左边,4 排在右边
jM1kv6P
KJZMxvE

但此时,基准点 3 的左边是未排序的数列
Py6XtgV

所以在未排序的数列中,再随机取一值为基准点,下图取 2 为基准点,因为 1 < 2 ,所以 1 要排在基准点 2 的左边。
2T9ylO8
e8S8KMM

基准点 3 的右边也是未排序的数列
egXKFGh

随机取基准点为 5 ,因 4 < 5 ,所以 4 排在基准点 5 的左边
GGtLF2h
RKSp1hG

最後确定所有基准点左右都排序完成後,排序就结束了~
TEMwd3J

参考资料:

演算法笔记:Sort
[演算法] 排序演算法(Sort Algorithm)


好的~今天就先到这边啦!大家梦里见~还有明天见~掰掰~~


<<:  2.4.6 Design System - Carousel

>>:  Day 30-单元测试(结尾)

Day 28 Rails shallow nesting

阿修说文解字 甚麽是 shallow nesting? shallow nesting 是用来把路径...

鼠年全马铁人挑战 WEEK 34:负载性能测试 - Gatling (上)

           Photo on gatling.io 前言 前几周小弟介绍了一款负载性能的...

予焦啦!使用 GDB 推进

本节是以 Golang 上游 ee91bb83198f61aa8f26c3100ca7558d30...

[Day23] HTB Buff

URL : https://app.hackthebox.eu/machines/263 IP :...

【Day12】系列终止

因为某种天外飞仙,天上掉下来的炸弹等的理由,所以这个项目就会终止,在报 名截止前让我想想要参加甚麽项...