wiki上的快排算法是不是有问题

水木社区手机版

主题:wiki上的快排算法是不是有问题
楼主|sixue1999|2022-01-30 04:50:52|只看此ID
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

其中原地切割算法

这段算法的逻辑也太蠢了吧
这不是相当于在快排的局部嵌套了一个冒泡吗？
--
FROM 120.244.236.*
1楼|littleSram|2022-01-30 09:44:08|只看此ID
没有一个回帖，然后是电脑技术版的热门帖子
【在 sixue1999 的大作中提到: 】
: https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
: 其中原地切割算法
: 这段算法的逻辑也太蠢了吧
: ...................
--
FROM 221.222.21.*
2楼|cybereagle|2022-01-30 13:24:54|只看此ID
只和pivot比大小，小于pivot的用一次交换移到左边
你确定这是冒泡？
【在 sixue1999 (宋似雪) 的大作中提到: 】
: https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
: 其中原地切割算法
: 这段算法的逻辑也太蠢了吧
: ...................
--
FROM 121.207.203.*
3楼|sixue1999|2022-02-03 05:01:53|只看此ID
不完全是冒泡
但是一个大于pivot的值，要把他移动到右侧，要交换n次
【在 cybereagle (2/3的沉默@XMUCSD) 的大作中提到: 】
: 只和pivot比大小，小于pivot的用一次交换移到左边
: 你确定这是冒泡？
--
FROM 120.244.236.*
4楼|thorware|2022-02-03 08:26:07|只看此ID
这个跟算法导论上是一样的

最多要交换n次而已，on的操作后列表就被分割成less和greater 了

快排的效率在于分治的效果，分割后是否能迅速减小问题的规模，不要把重点搞单科

【在 sixue1999 的大作中提到: 】
: 不完全是冒泡
: 但是一个大于pivot的值，要把他移动到右侧，要交换n次
: 【在 cybereagle (2/3的沉默@XMUCSD) 的大作中提到: 】
: ....................

- 来自「最水木 for iPhone14,5」
--
FROM 101.82.148.*
5楼|moudy|2022-02-03 17:22:43|只看此ID
best case nlog(n)
worst case n**2
你当n**2是怎么来的?

【在 sixue1999 的大作中提到: 】
: 不完全是冒泡
: 但是一个大于pivot的值，要把他移动到右侧，要交换n次
:
--
FROM 188.192.115.*