当前位置:网站首页>彩虹排序 | 荷兰旗问题
彩虹排序 | 荷兰旗问题
2020-11-09 12:28:00 【码农田小齐】
微信搜索「码农田小齐」,关注这个在纽约的程序媛,回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源,么么哒~
荷兰旗问题又称三色排序,或者彩虹排序,
因为荷兰旗就三种颜色嘛,那这道题的问题就是给你三种颜色,按照给定的顺序排好。
当然了,题目的问法各种各样,有的给数字,有的给字母,但本质都是一样的。
比如给你一个只含有三个数字的数组:312312312231111122113,
要求按照 1 2 3 的顺序排好,即: 111111111222222222223333333333
(请不要真的去数数,认真你就输了)
还是用我们经典的「挡板法」。
在快排中,我们用了两个挡板把数组分成三个区域:
<= pivot;未排序区间;> pivot
那么这里就要三个挡板,分成四个区域:
1, 2, 3, 未排序区间
Partition
具体说来,用 i, j, k 这三个指针分一下:
[0, i): 存 1
[i, j): 存 2
(k, array.length-1]: 存 3
这里 j 放在未排序区间的左边和右边都行,但基本上大家都是放左边,所以我们也没必要“标新立异”。
初始化:
i = 0;
j = 0;
k = array.length - 1;
这样才能保证 1,2,3 的每个区间都为空。
我们通过观察指针 j 指向的元素来不断缩小未排序区间,直到为空。
例子:1232312
为了好看,排好序的元素我们用 RGB 三原色标示一下。
Step1.
指针 j 指向 1,而 1 应该放在 [0, i) 区间内, 这里应该把指针 i 和指针 j 所指的元素交换一下,并且俩指针往前走。
虽然在这步看来是否交换没什么区别,但是如果 i 和 j 之间有元素,就有区别了,比如 Step7.
Step2.
指针 j 指向 2,而 2 应该放在 [i, j) 区间内,所以 j++.
Step3.
指针 j 指向 3,而 3 应该放在
(k, array.length-1] 区间内,所以这里
j 和 k 指向的元素交换一下,并且 k--.
注意这里就不能 j-- 了,因为新换回来的元素还没瞧呢,不知道它是几。
Step4.
指针 j 指向 2,同 Step2,直接移动指针 j 即可。
Step5.
继续移动指针 j。
Step6.
同 Step3.
Step7.
这一步就很明显看出来了,
由于 1 应该放在 [0,i) 区间,所以这里把指针 i,j 所指向的元素交换一下,并且 i++, j++.
这样未排序区间为空,我们就排好了~
时间复杂度
这个算法的 bottle neck 就在这个 while loop 里了,每次循环是 O(1),总共是 O(n).
空间复杂度
O(1)
如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!
我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!
更多干货文章见我的 Github: https://github.com/xiaoqi6666/NYCSDE
版权声明
本文为[码农田小齐]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4612374/blog/4708569
边栏推荐
- 开源ERP招聘了
- Chrome browser engine blink & V8
- 外贸自建网站域名的选择— Namesilo 域名购买
- Using rem, the font size changes when the screen zooms
- Depth analysis based on synchronized lock
- Git delete IML file
- Learning notes of nodejs
- Android 集成支付的四部曲
- iPhone“连到系统上的设备没有发挥作用”原因分析及解决方法 20200105
- How to query by page after 10 billion level data is divided into tables?
猜你喜欢
How to query by page after 10 billion level data is divided into tables?
An attempt to read or write to protected memory occurred using the CopyMemory API. This usually indicates that other memory is corrupted.
Show profile analysis of SQL statement performance overhead
Android studio AVD
微信圈子
Understanding data structures starts with this article~
Python zero basics tutorial (01)
Kubernetes业务日志收集与监控
Is SEO right or wrong?
Dynamo: a typical distributed system analysis
随机推荐
开源ERP招聘了
零基础IM开发入门(四):什么是IM系统的消息时序一致性?
Nine kinds of distributed primary key ID generation schemes of sub database and sub table are quite comprehensive
Dynamo: a typical distributed system analysis
嗯,查询滑动窗口最大值的这4种方法不错....
Using rem, the font size changes when the screen zooms
Handwritten digital image recognition convolution neural network
为wget命令设置代理
JVM学习(四)-垃圾回收器和内存分配
分库分表的 9种分布式主键ID 生成方案,挺全乎的
Program life: from Internet addicts to Microsoft, bat and byte offer harvesters
接口测试如何在post请求中传递文件
For and for... In, for each and map and for of
关于无相互作用极化率的计算
Safety (miscellany)
Handwriting Koa.js Source code
A simple way to realize terminal text paste board
Android权限大全
Glsb involves load balancing algorithm
苏宁基于知识图谱的大规模告警收敛和根因定位实践