搜索

[27445] 2020-02-06_Rust算法排位记-选择排序图示与代码实现

文档创建者：s7ckTeam
浏览次数：32
最后更新：2025-01-19
2020-02-06_Rust算法排位记-选择排序图示与代码实现 R u s t   算 法 排 位 记 - 选 择 排 序 图 示 与 代 码 实 现 原 创   韦 世 东   N i g h t T e a m   2 0 2 0 - 0 2 - 0 6 聊 胜 于 无 聊 胜 于 无 以 下 是 来 自 菜 鸟 教 程 中 的 排 序 过 程 和 图 示 ： 首 先 在 未 排 序 序 列 中 找 到 最 小 （ 大 ） 元 素 ， 存 放 到 排 序 序 列 的 起 始 位 置 。 再 从 剩 余 未 排 序 元 素 中 继 续 寻 找 最 小 （ 大 ） 元 素 ， 然 后 放 到 已 排 序 序 列 的 末 尾 。 重 复 直 到 所 有 元 素 均 排 序 完 毕 。 我 们 来 捋 一 捋 ， 选 择 排 序 的 主 要 逻 辑 为 ： 1 . 外 循 环 先 指 定 一 个 数 ， 通 常 是 第 一 个 数 2 . 接 着 在 内 循 环 中 将 这 个 外 循 环 指 定 数 与 右 侧 数 逐 个 比 较 ， 记 录 下 右 侧 数 当 中 最 小 的 那 位 3 . 左 侧 为 排 序 好 的 元 素 ， 遂 内 循 环 中 的 比 较 是 外 循 环 指 定 数 不 停 地 与 右 侧 元 素 进 行 比 较 4 . 内 循 环 时 ， 每 次 发 现 比 外 循 环 指 定 数 小 的 数 就 记 录 下 来 ， 循 环 结 束 后 记 录 的 数 便 是 右 侧 最 小 数 5 . 在 内 循 环 结 束 后 将 外 循 环 指 定 数 与 内 循 环 得 出 的 右 侧 最 小 数 交 换 位 置 6 . 依 此 类 推 ， 直 到 外 层 循 环 结 束 现 在 有 一 组 需 要 排 序 的 元 素 ： 按 照 选 择 排 序 的 逻 辑 外 循 环 指 定 下 标 为   0   的 第 一 个 数   7 ， 选 定 后   f o r   循 环 将 从 下 标 为   0   的 元 素 开 始 循 环 。 代 码 表 现 为 ： f o r   循 环 从 下 标 为   0   的 第 一 个 数   7   开 始 。 在 内 循 环 中 将 这 个 外 循 环 指 定 数 与 右 侧 数   [ 2 1 ,   9 ,   1 3 ,   1 0 9 ,   9 ,   2 ,   5 0 ,   3 3 ,   - 1 ,   2 0 ,   1 1 ]   逐 个 比 较 ， 当 外 循 环 指 定 数 小 于 左 边 元 素 时 记 录 最 小 值 ， 内 循 环 结 束 后   v e c t o r s [ i ]   与   v e c t o r s [ j ]   交 换 位 置 。 本 轮 最 小 数 为   - 1 ， 遂 [ 7 ,   2 1 ,   9 ,   1 3 ,   1 0 9 ,   9 ,   2 ,   5 0 ,   3 3 ,   - 1 ,   2 0 ,   1 1 ] f o r   i   i n   0 . . v e c t o r s . l e n ( ) { }
元 素 组 变 为 ： [ - 1 ,   2 1 ,   9 ,   1 3 ,   1 0 9 ,   9 ,   2 ,   5 0 ,   3 3 ,   7 ,   2 0 ,   1 1 ] 此 时 进 入 下 一 轮 外 循 环 下 一 轮 外 循 环 ， 指 定 下 标 为   1   的 第 二 个 数   2 1 。 在 内 循 环 中 将 这 个 外 循 环 指 定 数 与 右 侧 数   [ 9 ,   1 3 ,   1 0 9 ,   9 ,   2 ,   5 0 ,   3 3 ,   - 1 ,   2 0 ,   1 1 ]   逐 个 比 较 ， 当 外 循 环 指 定 数 小 于 左 边 元 素 时 记 录 最 小 值 ， 内 循 环 结 束 后   v e c t o r s [ i ]   与   v e c t o r s [ j ]   交 换 位 置 。 本 轮 最 小 数 为   2 ， 遂 元 素 组 变 为 ： [ - 1 ,   2 ,   2 1 ,   1 3 ,   1 0 9 ,   9 ,   9 ,   5 0 ,   3 3 ,   7 ,   2 0 ,   1 1 ] 以 此 规 则 类 推 ， 元 素 排 序 的 最 终 结 果 为 ： 具 体 代 码 实 现 具 体 代 码 实 现 首 先 定 义 一 组 元 素 ， 并 打 印 ： 然 后 定 义 排 序 方 法 ： 排 序 方 法 的 外 循 环 是   f o r   循 环 ： 这 里 的   i n d e x   代 表 最 小 值 的 下 标 ： 在 内 循 环 中 的 将 外 循 环 指 定 数 与 右 侧 数 逐 个 比 较 ， 当 外 循 环 指 定 数 小 于 右 侧 元 素 时 记 录 右 侧 元 素 的 下 标 ， 否 则 不 动 。 不 停 地 与 右 侧 元 素 比 较 用   f o r   j   i n   i + 1 . . v e c t o r s . l e n ( )   和   v e c t o r s [ j ]   <   v e c t o r s [ i n d e x ]   表 示 ； [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 1 ,   1 3 ,   2 0 ,   2 1 ,   3 3 ,   5 0 ,   1 0 9 ] f n   m a i n ( )   {         l e t   m u t   v e c t o r s   =   v e c ! [ 7 ,   2 1 ,   9 ,   1 3 ,   1 0 9 ,   9 ,   2 ,   5 0 ,   3 3 ,   - 1 ,   2 0 ,   1 1 ] ;         p r i n t l n ! ( " v e c t o r s :   { : ? } " ,   v e c t o r s ) ; } f n   i n s e r t _ s o r t ( v e c t o r s :   & m u t   V e c < i 3 2 > )   - >   & V e c < i 3 2 > {                 v e c t o r s } f n   i n s e r t _ s o r t ( v e c t o r s :   & m u t   V e c < i 3 2 > )   - >   & V e c < i 3 2 > {                 f o r   i   i n   0 . . v e c t o r s . l e n ( ) {         }                 v e c t o r s } f n   i n s e r t _ s o r t ( v e c t o r s :   & m u t   V e c < i 3 2 > )   - >   & V e c < i 3 2 > {                 f o r   i   i n   0 . . v e c t o r s . l e n ( ) {                         l e t   m u t   i n d e x   =   i ;         }                 v e c t o r s }
下 标 的 记 录 其 实 可 以 用 交 换 代 替 ， 这 样 内 层   f o r   循 环 结 束 时 ， i n d e x   一 定 是 右 侧 中 小 元 素 的 下 标 ； 交 换 位 置 无 法 像   P y t h o n   那 样   a ,   b   =   b ,   a ， 只 能 用   c   =   a ,   a   =   b ,   b   =   c   这 种 加 入 第 三 个 数 的 方 式 倒 腾 。 遂 代 码 如 下 理 论 的 验 证 理 论 的 验 证 上 面 的 理 论 看 似 有 理 有 据 令 人 信 服 ， 但 究 竟 对 不 对 呢 ？ 我 们 可 以 通 过 打 印 程 序 执 行 过 程 中 每 一 轮 的 轮 次 、 最 小 值 和 当 前 元 素 组 。 添 加 了 打 印 语 句 的 代 码 如 下 ： 代 码 运 行 后 的 打 印 结 果 如 为 ： f n   s e l e c t i o n _ s o r t ( v e c t o r s :   & m u t   V e c < i 3 2 > )   - >   & V e c < i 3 2 > {         f o r   i   i n   0 . . v e c t o r s . l e n ( ) {                 / /   寻 找 未 排 序 元 素 中 的 最 小 值 ， 即 [ i ,   n ) 中 的 最 小 元 素                 l e t   m u t   i n d e x   =   i ;                 f o r   j   i n   i + 1 . . v e c t o r s . l e n ( ) {                         i f   v e c t o r s [ j ]   <   v e c t o r s [ i n d e x ] {                                 i n d e x   =   j ;                         }                 }                 l e t   m i d d l e   =   v e c t o r s [ i n d e x ] ;                 v e c t o r s [ i n d e x ]   =   v e c t o r s [ i ] ;                 v e c t o r s [ i ]   =   m i d d l e ;         }         v e c t o r s } f n   s e l e c t i o n _ s o r t ( v e c t o r s :   & m u t   V e c < i 3 2 > )   - >   & V e c < i 3 2 > {         f o r   i   i n   0 . . v e c t o r s . l e n ( ) {                 / /   寻 找 未 排 序 元 素 中 的 最 小 值 ， 即 [ i ,   n ) 中 的 最 小 元 素                 l e t   m u t   i n d e x   =   i ;                 f o r   j   i n   i + 1 . . v e c t o r s . l e n ( ) {                         i f   v e c t o r s [ j ]   <   v e c t o r s [ i n d e x ] {                                 i n d e x   =   j ;                         }                 }                 p r i n t l n ! ( " 现 在 是 第   { }   轮 ,   最 小 值 :   { } ,   v e c t o r s :   { : ? } " ,   i ,   v e c t o r s [ i n d e x ] ,   v e c t o r s ) ;                 l e t   m i d d l e   =   v e c t o r s [ i n d e x ] ;                 v e c t o r s [ i n d e x ]   =   v e c t o r s [ i ] ;                 v e c t o r s [ i ]   =   m i d d l e ;         }         v e c t o r s } 现 在 是 第   0   轮 ,   最 小 值 :   - 1 ,   v e c t o r s :   [ 7 ,   2 1 ,   9 ,   1 3 ,   1 0 9 ,   9 ,   2 ,   5 0 ,   3 3 ,   - 1 ,   2 0 ,   1 1 ] 现 在 是 第   1   轮 ,   最 小 值 :   2 ,   v e c t o r s :   [ - 1 ,   2 1 ,   9 ,   1 3 ,   1 0 9 ,   9 ,   2 ,   5 0 ,   3 3 ,   7 ,   2 0 ,   1 1 ] 现 在 是 第   2   轮 ,   最 小 值 :   7 ,   v e c t o r s :   [ - 1 ,   2 ,   9 ,   1 3 ,   1 0 9 ,   9 ,   2 1 ,   5 0 ,   3 3 ,   7 ,   2 0 ,   1 1 ] 现 在 是 第   3   轮 ,   最 小 值 :   9 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   1 3 ,   1 0 9 ,   9 ,   2 1 ,   5 0 ,   3 3 ,   9 ,   2 0 ,   1 1 ]
由 此 可 见 ， 理 论 部 分 的 描 述 是 正 确 的 ， 即 每 轮 次 将 右 侧 元 素 中 的 最 小 值 与 当 前 轮 次 元 素 的 位 置 交 换 。 完 整 的   R u s t   选 择 排 序 代 码 如 下 ： 现 在 是 第   4   轮 ,   最 小 值 :   9 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   1 0 9 ,   1 3 ,   2 1 ,   5 0 ,   3 3 ,   9 ,   2 0 ,   1 1 ] 现 在 是 第   5   轮 ,   最 小 值 :   1 1 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 3 ,   2 1 ,   5 0 ,   3 3 ,   1 0 9 ,   2 0 ,   1 1 ] 现 在 是 第   6   轮 ,   最 小 值 :   1 3 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 1 ,   2 1 ,   5 0 ,   3 3 ,   1 0 9 ,   2 0 ,   1 3 ] 现 在 是 第   7   轮 ,   最 小 值 :   2 0 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 1 ,   1 3 ,   5 0 ,   3 3 ,   1 0 9 ,   2 0 ,   2 1 ] 现 在 是 第   8   轮 ,   最 小 值 :   2 1 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 1 ,   1 3 ,   2 0 ,   3 3 ,   1 0 9 ,   5 0 ,   2 1 ] 现 在 是 第   9   轮 ,   最 小 值 :   3 3 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 1 ,   1 3 ,   2 0 ,   2 1 ,   1 0 9 ,   5 0 ,   3 3 ] 现 在 是 第   1 0   轮 ,   最 小 值 :   5 0 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 1 ,   1 3 ,   2 0 ,   2 1 ,   3 3 ,   5 0 ,   1 0 9 ] 现 在 是 第   1 1   轮 ,   最 小 值 :   1 0 9 ,   v e c t o r s :   [ - 1 ,   2 ,   7 ,   9 ,   9 ,   1 1 ,   1 3 ,   2 0 ,   2 1 ,   3 3 ,   5 0 ,   1 0 9 ]
R u s t   算 法 代 码 仓 库 地 址   h t t p s : / / g i t h u b . c o m / a s y n c i n s / a c r u s t
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理