网站建设做网站需要多少钱?,开微信小程序要钱吗,中小企业公共服务平台网站建设,wordpress安装不了#x1f600;前言 在数据结构面试中#xff0c;排序算法是考察重点之一。传统的排序算法#xff0c;例如冒泡排序、快速排序等#xff0c;都依赖于元素之间的比较和交换操作。然而#xff0c;在某些情况下#xff0c;我们可能只允许使用特定的交换操作#xff0c;例如只… 前言 在数据结构面试中排序算法是考察重点之一。传统的排序算法例如冒泡排序、快速排序等都依赖于元素之间的比较和交换操作。然而在某些情况下我们可能只允许使用特定的交换操作例如只能与0交换。在这种情况下传统的排序算法就不再适用 个人主页尘觉主页
数据结构面试常见问题之- Sort with Swap(0,*)
习题-SWS.1 环的分类
题意理解
给定N个数字的排列如何仅利用与0交换达到排序目的 0在里面扮演了空位的问题
环的分类
环分3种
只有1个元素:不需要交换环里no个元素包括0:需要no-1次交换第i个环里有ni;个元素不包括0: 先把0换到环里再进行(ni1)-1次交换 – 一共是n;1次交换
若N个元素的序列中包含S个单元环、K个多元环则交换次数为: n 0 − 1 ∑ i 1 K − 1 ( n 1 1 ) n_0 - 1 \sum_{i1}^{K-1} (n_1 1) n0−1i1∑K−1(n11) ∑ i 0 k − 1 n 1 K − 2 N − S K − 2 \sum_{i0}^{k-1} n_1 K - 2 N - S K - 2 i0∑k−1n1K−2N−SK−2
习题-SWS.2 算法示例 对于不包含0的swap操作次数为n1包含0则是n-1次
总结
本文介绍了一种基于环的分类方法用于解决仅允许与0交换的排序问题。该方法将元素划分为不同的环并根据环的类型计算所需的交换次数。最后通过示例演示了该方法的应用。 祝福您面试顺利
热门专栏推荐 想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集 linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
欢迎大家加入我的社区 尘觉社区 文章到这里就结束了如果有什么疑问的地方请指出诸佬们一起来评论区一起讨论 希望能和诸佬们一起努力今后我们一起观看感谢您的阅读 如果帮助到您不妨3连支持一下创造不易您们的支持是我的动力
