Tip:
Highlight text to annotate it
X
这段视频中 我想探讨
一种更直观的排序方法
这是我徒手排序时最可能采用的方法
但我想澄清的是
这不是最高效的排序方式
但是咱们就先
我觉得这是个好的开始
咱们可以由此为排序先热热身
该方法叫做插入排序
我将给出图示说明
来解释插入排序算法
你要知道
算法这个词听着很神奇
但(排序)算法其实只是排序的一种手段
一个过程
或一种方法
程序则是特定算法的具体实现
或者可以作为某个算法的具体实现
一旦有了某个通用的算法
我可以用 Python 实现它
可以用 C 实现它
可以用 Java 实现它
那些都是具体的程序
而它们都实现了
同一种排序方式
也就是我所说的
插入排序算法
咱们从一个简单的例子开始
假设我有一个列表
假设我有一个 Python 中的列表
因为我们要用 Python 实现该算法
该列表是
就说它是 [7,3,1,2,4,6]
那么我们做插入排序的方式就是
依次检查每个元素
将该元素与它前边的多个元素进行比较
当你找到它前边第一个不小于它的元素
当你找到它前边第一个不小于它的元素
你就把它固定在那儿
我来示范一下上述过程
你可以从7入手
这里的第0个元素
但当你审视
当你从第0个元素开始时
你会发现 等一下 它前边没什么可以比较的
所以从第0个元素开始毫无意义
说真的 如果你要实现这个算法
你最好从第 [1] 个元素开始
抱歉 你从
如果这是第0个元素
你从这里的第1个元素开始
这是第0个 这是第1个 我很清楚
如果你把它当成第1个元素 你会很困惑
但这是第0个
所以你从这里的3开始
你开始将它与它前边的所有元素进行比较
一旦发现某个不小于3的元素
你就把它固定在列表的那个部分
于是你所要做的就是设问
好的 3小于7吗
喔是的 小于7
所以你要做的就是交换
把7换到3的位置
我把它提出来放这儿
我们正在
我们正试着将3和它之前的所有元素进行比较
我们正试着将3和它之前的所有元素进行比较
所以你说 好的 3比7小吗
是啊 它小于7
所以咱们把7放在3的位置
把3放在7的位置
因为前边没剩下其他元素可以与3比较
前头没了
第0个元素前边没有元素了
所以咱们就把3固定在那儿
至此我们的列表看起来像这样
我们的列表现在看上去是 [3,7,1,2,4,6]
你会发现一件有趣的事
有些地方需要注意
在我们生成这个列表的时候
现在第0个元素肯定小于第1个
(从开头)到包括第1个元素在内的所有元素
现在已经是有序的了
(从开头)到包括第1个元素在内的所有元素
现在已经是有序的了
随着我们继续进行 这一特点将会一直成立
随着我们处理下标更加靠后的元素
一直到包括该下标元素在内的所有元素
在我们完成那一趟排序后 都将是有序的
接下来我会随时指出这一点
我们处理过了第1个下标
现在可以继续处理第2个元素了
也就是这个1
于是你把这个1
我会把它放在一边
你提出这个1
并将它与它前边的每一个元素进行比较
那么1比7小吗
当然 1小于7
所以咱们把7固定在1那儿
然后你既可以继续比较
也可以先把1固定在7的位置
然后继续比较 1比3小吗
肯定啊 它是小于3
所以咱们将3固定在1那儿
并且把1放到3的位置
那现在我们的列表成什么样了
我们的列表现在看起来
我们的列表现在是 [1,3,7,2,4,6]
注意 在我们到达第 n 个索引后
本例中是索引2
也就是1早先所在的地方
从头到包括该索引的每个元素已经有序
这一部分已经有序
它将会是
接下来 其他元素也将陆续被扔进这一部分
接下来 其他元素也将陆续被扔进这一部分
目前为止这部分已经有序了
你可以看到
当我们到达列表结尾的时候
一切都会排列有序
那咱们就来处理下一个索引
或者说列表中的下一项
也就是这里的2
也就是这里的2
我们拿2和7比
2肯定小于7
所以咱们把7放在2的位置
把2放在7那儿
现在比较2和3
2小于3
咱们就把3放在2的位置
并且把2放在3的位置
然后比较2和1
2比1小吗
它不小于1
所以我们不需要再做什么了
我们不必继续往左边考察了
至此 在这一趟排序之后
本趟排序中我们用2这一项
与它前边的所有元素进行比较
在这趟排序之后 我们的列表看起来像这样
我们的列表看起来像 [1,2,3,7,4,6]
注意到 从头开始到包括第3项在内的所有元素
第0 1 2 3个项
现在已经有序了
现在我们可以继续考察
列表中的下一个元素
我想澄清一件事
当你真正实现它的时候
可以采取很多种方法
你不用总是
在此示例中 我们说
嘿 2小于7吗
于是7取代了2的位置
这是你应该做的
然后我们让2取代了7的位置
但现实是
你可以一直向左
直到你找到适合2的好位置
然后把其他元素移到右边
再把2放进去
尽管咱们的方式更容易理解
也许我们将探索不同的方法来做排序
等到我们真的要实现本算法时再说
好了 咱们看看这个4
(跟先前)完全一致的想法
4小于7
所以咱们把7放在4的位置
把4放在7那儿
4比3小吗
4不小于3
所以到此为止 咱们完成了
现在 包括第4项在内的前边所有元素
在列表中的第0 1 2 3 4项
现在已经有序
现在我们的列表看起来像
让我向下滚动一点
我们的列表看起来像这样
你把它写下来
就是 [1,2,3,4,7,6]
现在我们可以转到此列表中的最后一个元素
也就是我们现在正要比较的6
这是我们最后一次进行比较
就像之前针对4所做的
但现在我们关注的是6
6比7小吗 肯定的
于是咱们把7放在6的位置
并把6放在7那儿
6比4小吗 并非如此
我们就此停住
因为我们知道排序将要完成
如果我们还要往前找 我们只会得到
我们只会得到不大于4的元素
所以我们完成了 此列表排序完毕
排序后的列表现在是 [1,2,3,4,6,7]
在下一个视频中
我要真正尝试实现
我刚刚描述的这种算法
我将会用一个简单的 Python 函数实现它