【算法学习】趁热打铁,插入,选择和归并排序

插入排序

插入排序最直观的解释是不断拿扑克牌时排序的动作。一开始你只有一张8,第二张是5,你把5放在8的左边。第三张是9,你放在8的右边。第四张是2,你放在最左边。拿这四张牌的过程可以认为是排序4个数字的过程。步骤可以归纳为:

  • 拿起一张牌 -> 取下一个数
  • 比较现有牌,具体来说是从右往左找到第一个不小于当前牌的位置 -> 将所有大于当前数的数字向右移动一位
  • 放入牌 -> 放置数字

形象上来讲,放置数字的过程是多个数字右移的过程,所以不需要swap。Java代码如下:

实际实现中,认为第一个数字即你只有一张牌的时候肯定是排好序的,所以插入牌的过程从第二个数字开始。注意着重看while部分,这就是大于当前数的数字右移的过程。

选择排序

现在理解起来其实不是很难的算法。之前没学好有可能是因为数据结构课太无聊,对数据结构课无爱……
核心想法是选择第一个小的数放在第一位,再在剩下的数字中选择第二小的数字放在第二位,依次类推。
理论上只看这些的话和冒泡排序很像,但是选择排序的特点是交换次数少,因为只记录下标,冒泡排序直接交换。Java代码如下:

注意选择排序只记录最小数字的下标,即min,swap理论上最多发生n次。

归并排序

如果理解了两个已排序的序列如何合并的过程的话基本上不难了。
归并排序的想法是把数组拆分为两个数组,排序这两个数组,再合并。过程中不断递归,直到只有1个元素。一个元素肯定是排序好的。然后向上回溯,由合并过程合并两个排序好的数组直到原始大小。
实际实现中,合并逻辑的两个输入数组是原始数组的两个邻接区间,其次有一个中间数组用来放置合并逻辑的输出。在回溯时要把中间数组的内容复制回原始数组。Java代码如下:

说一下合并逻辑,对两个输入数组或者一个数组的两个区间([leftBegin, leftEnd], [rightBegin, rightEnd],因为是邻接的,所以rightBegin = leftEnd + 1),取两个数组的头一个元素比较,选择小的放入输出数组(ms),提供小数字的数组位置加1,依次类推。在第一个while结束时,肯定有一个数组的数字选完了。接下来要把生下来的数字放入输出数组。
排序的递归逻辑中最后一句是必须的,否则你等于没排序……这里使用了Java的System.arrayCopy,比逐个复制速度快。

到现在为止,学习的排序都是不需要特别的数据结构的,接下来可能要“复习”一下堆结构学习堆排序。