javascript实现排序算法（四）

上面三篇博客介绍了排序算法中属于交换排序思想的快速排序和冒泡排序，以及选择排序中的简单选择排序。今天要介绍的并不是选择排序的另一种堆排序，因为堆排序的算法比较复杂，而且需要使用javascript实现一种非线性的数据结构：树。在以后的博客中，我会在讲堆排序之前，专门拿出一篇博客来介绍树以及二叉树在javascript中的应用。我觉得先易后难，由浅入深是知识学习最佳的方式。

复习一下前两类排序算法的排序过程和思想。首先，交换排序的核心思想就是每次遍历，会把小的值换到左边，大的值换到右面，循环往复所有左边的值都不大于右边的值，这样就成了一个有序的数组；选择排序呢，每次遍历数组，将最小值选出来，放到第一个，然后再选剩下的当中的最小值放到第二个，一次类推直到剩下的数组长度为一，那自然前面的数组就都是有序的。今天要介绍的是排序算法中的另一大类，插入排序。

我相信大多数人应该都打过扑克牌，不同的地方玩法不一样，但是不管你玩的是什么规则的，前两步都是一样的，那就是抓牌和码牌。不管你是变抓变码还是抓完之后在进行码牌的操作。在码牌的过程中你就一定默默地用到了插入排序的思想。详细来说，一副牌在你的手里，你需要将他们排成你想要的顺序，我相信没有人能像变魔术一样，上一秒还杂乱无章，吹口仙气就能把牌变成井然有条。每个人都是一张一张的将牌放到他该出现的位置，比如大一点的牌或者大小王经常会被先放到两边，而6，7，8这样的牌会被放到中间，这个放的过程又可以被称为将一张牌重新插入牌堆的过程，这个过程就是插入排序。

接下来介绍插入排序详细的步骤：

1、确定一个需要重新插入的元素，在一个范围内对这个元素和其他的元素进行比较，如发现有比这个元素小的元素，将待插入的元素插入到这个元素的前面。

2、将这个范围扩大，重复上面的操作。

在写完上面那两点之后，用宋小宝的话来说，我自己看着都有点蒙圈了，这里举个例子来解释一下这个过程，比如，待排序的数组是5，4，3，2，1。首先选则带插入的元素，这里选第二个元素，原因是，接下来的逻辑用这个元素和它的左边元素进行比较，如果发现左边的元素大于我们选得这个元素就把它插到这个元素的左边。在插入之后这个元素就已经完成它的使命了。我们再进行第一次插入排序之后得到的数组就是4，5，3，2，1。然后继续选择待排序的元素3，发现4，5都比它大，那自然他就插到4，5的前面，得到了3，4，5，2，1这个数组，以此类推，2插到3前面，1插到2前面，这个时候我们就通过一次次插入的过程将无序的数组转化为有序的集合。接下来还是使用代码进行实现。

首先定义一个插入排序方法，校验传入数组的长度

function insertSort(arr) {

     if(arr.length<2){

        return arr;

      }

｝

遍历整个数组

for(var i = 1;i<arr.length;i++){

  var j = i;

  var temp = arr[i];

}

这里需要记录下来待插入的元素，以及它的位置，因为在后面要执行插入操作，需要保存这个元素，以及通过这个元素的索引来与它前面的元素进行比较。接下来就是插入操作了。

while(j>0 && arr[j-1]>temp){

     arr[j] = arr[j-1];

      j--;

}

arr[j] = temp;

这里面的while循环其实就是上面所说的在一个范围内比较，也就是与待插入元素左面元素进行比较，当他左面还有值可以比并且当它左面的值大于它的值，那么将它左面的值右移一位，以此类推，如果条件符合的元素左移一位，细心的朋友可能发现了只有它的值就被覆盖了，最后会出现两个一样的值，就和上面我举得那个例子一样，其实在第一次插入排序结束之前，数组其实是5，5，3，2，1可以发现待插入的值被覆盖了，这里就是前面需要用一个temp变量保存这个元素的原因。其他元素左移，它插到了那个元素原来的位置，这就是模拟插入的过程。是不是很像码牌的过程。

插入排序的算法就讲到这里，讲了四个算法不知道大家有没有发现，其实这四个算法是你中有我，我中有你。比如在选择排序的时候，也用到了交换，每次交换将最小的元素放到了前面，快速排序的时候也用到了选择，选出比基准小的元素放到基准左边，比基准大的元素放到基准的右面。而今天讲到的插入排序同样也用到了选择和交换的思想。也许排序的算法远远不止这几种，但是万变不离其宗，我认为这也就是我在前几篇博客中提到的，编程的思想如果掌握了，学任何的语言，技术都是手到擒来的事情。而基础不牢，学再多的技术也许只是知其然而不知其所以然，这也正是我最欠缺的，希望与大家一起学习，一起进步，感谢阅读。