我正在学习 Rust 语言
Rust 代码在编写过程中与其它语言的略有不同,因为它的编译器不允许有任何不安全的写法,遂代码编写过程中花费时间最长的莫过于查找编译报错的原因。这样也有好处——代码写好之后,稳定性高得一笔!
以下是来自菜鸟教程中的排序定义和示意图:
插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
我们来捋一捋,插入排序的主要逻辑为:
1.外循环先指定一个数,通常是第一个数2.接着在内循环中将这个外循环指定数与左侧数逐个比较,并根据比较结果将外循环指定数插入在内循环数的左边或不动3.左侧为排序好的元素,遂内循环中的比较是外循环指定数不停地与左侧元素进行比较4.当外循环指定数小于左侧元素时交换位置,否则不动5.以此类推,直到外层循环结束
现在有一组需要排序的元素:
按照插入排序的逻辑外循环指定第一个数7,选定后 for 循环将从下标为 1 的元素开始循环。代码表现为:
下标为的第一个数7是排序好的,那么 for 循环从下标为1的第二个数21开始。在内循环中将这个外循环指定数与左侧数 [7] 逐个比较,当外循环指定数小于左边元素时交换位置,否则不动。
此时进入下一轮外循环,指定下标为2的第三个数9。在内循环中将这个外循环指定数与左侧数 [7, 21] 逐个比较,当外循环指定数小于左边元素21时交换位置,遇到7不动。遂元素组变为 :
[7,9,21, 13, 109, 9, 2, 50, 33, -1, 20, 11]
此时进入下一轮外循环,指定下标为3的第四个数13。在内循环中将这个外循环指定数与左侧数 [7, 9, 21] 逐个比较,当外循环指定数小于左边元素21时交换位置,遇到9不动。遂元素组变为 :
[7, 9,13,21, 109, 9, 2, 50, 33, -1, 20, 11]
依此类推 ...
此时进入第 N 轮外循环,指定下标为5的第六个数9。在内循环中将这个外循环指定数与左侧数 [7, 9, 13, 21, 109] 逐个比较:
•当外循环指定数小于左边元素109时交换位置;•当外循环指定数小于左边元素21时交换位置;•当外循环指定数小于左边元素13时交换位置;
遇到9不动。遂元素组变为 :
[7, 9, 9,13,21,109, 2, 50, 33, -1, 20, 11]
此时进入第 N 轮外循环,指定下标为6的第七个数2。在内循环中将这个外循环指定数与左侧数 [7, 9, 9, 13, 21, 109] 逐个比较:
•当外循环指定数小于左边元素109时交换位置;•当外循环指定数小于左边元素21时交换位置;•当外循环指定数小于左边元素13时交换位置;•当外循环指定数小于左边元素9时交换位置;•当外循环指定数小于左边元素9时交换位置;•当外循环指定数小于左边元素7时交换位置;
遍历至元素组左侧尽头,此时 j 不大于等于 0,内循环结束。遂元素组变为 :
[2,7,9,9,13,21,109, 50, 33, -1, 20, 11]
在此之前,2 的左侧有很多元素,它需要与这些元素逐个比较并交换位置。数字 2 的位置变化过程如下:
从过程中可看到,内循环的每一轮,数字 2 都会往左移动,直到前面没有比 2 大的数字。
以此规则类推,元素排序的最终结果为:
具体代码实现
首先定义一组元素,并打印:
然后定义排序方法:
排序方法的外循环是 for 循环:
这里将外层元素赋值给可变变量 current,同时设定内循环左侧元素的下标:
在内循环中的将这个外循环指定数与左侧数逐个比较,当外循环指定数小于左侧元素时交换位置,否则不动。
与左侧元素比较用 j = i - 1, vectors[j] 表示;
不停地与左侧元素比较用 while j >= 0, j = j -1 表示;
比较用 current
交换位置无法像 Python 那样 a, b = b, a,只能用 c = a, a = b, b = c 这种加入第三个数的方式倒腾。遂代码如下
不过这样写的话,外循环指定数为比左侧所有数都小的情况下会无法通过编译的。例如外循环指定数为 2 时需要与左侧所有数进行比较,直到 j = 0,但 while 中最后一句是 j = j - 1,运行到这里后 j = -1。按照正常运行流程,程序会进入到下一轮 while j >= 0 的内循环,但由于 j = -1,就不会进入 while 循环体。Python 语言这样写是没问题的,但 Rust 的编译器不允许,遂需要在 j = j - 1 外层增加控制语句 if j = 0。
理论的验证
上面的理论看似有理有据令人信服,但究竟对不对呢?
有没有可能分析错误呢?
虽然程序是对的,但万一描述出来的逻辑有误呢?
我们可以通过打印程序执行过程中的外循环指定数 current、内循环左侧第一个数和每次交换位置后元素组 vectors 来观察循环比较时元素位置的变化情况。添加了打印语句的代码如下:
代码运行后的打印结果如为:
由此可见,理论部分的描述是正确的
完整的 Rust 插入排序代码如下:
领取专属 10元无门槛券
私享最新 技术干货