当前位置:网站首页>彩虹排序 | 荷兰旗问题
彩虹排序 | 荷兰旗问题
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/4708570
边栏推荐
- 解决IDEA快捷键 Alt+Insert 失效的问题
- A simple ability determines whether you will learn!
- 关于无相互作用极化率的计算
- 微信圈子
- Looking for better dynamic getter and setter solutions
- For and for... In, for each and map and for of
- 真正拖垮你的,是沉没成本
- 天啦撸!打印日志竟然只晓得 Log4j?
- Gather in Beijing! Openi / O 2020 Qizhi Developer Conference enters countdown
- 【分布式】分布式锁都有哪些实现方案?
猜你喜欢
android studio AIDL的使用
关于无相互作用极化率的计算
Download Netease cloud music 10W + music library with Python
Configure switch trunk interface traffic local priority forwarding (cluster / stack)
Reading design patterns adapter patterns
Interview summary on November 7, 2020 (interview 12K)
Interface tests how to pass files in post requests
EFF 认为 RIAA 正在“滥用 DMCA”来关闭 YouTube-DL
JVM学习(六)-内存模型和线程
Is SEO right or wrong?
随机推荐
Safety (miscellany)
inet_ Pton () and INET_ Detailed explanation of ntop() function
Show profile analysis of SQL statement performance overhead
Reread reconstruction
共创爆款休闲游戏 “2020 Ohayoo游戏开发者沙龙”北京站报名开启
通配符SSL证书应该去哪里注册申请
iPhone“连到系统上的设备没有发挥作用”原因分析及解决方法 20200105
大型项目Objective-C - NSURLSession接入短信验证码应用实例分享
After SQL group query, get the first n records of each group
Handwriting Koa.js Source code
如何用函数框架快速开发大型 Web 应用 | 实战
Solve the problem of idea shortcut key Alt + insert invalid
The choice of domain name of foreign trade self built website
The middle stage of vivo Monkey King activity
JVM learning (5) - execution subsystem
SQL Chapter 2 Chapter 3
Explain Python input() function: get user input string
Visit Jingdong | members of Youth Innovation Alliance of China Academy of space technology visit Jingdong headquarters
An attempt to read or write to protected memory occurred using the CopyMemory API. This usually indicates that other memory is corrupted.
New features of Fedora 33 workstation