算法之插入排序

背景

 

 

    当前存在排序的方法,这里以插入排序为例子,分析一个算法产生的过程。

 

问题描述

 

    有这么一个n个数的输入,我们希望的输出是一个有序的集合。

 

算法描述

 

    插入排序算法是对少量元素进行排序的有效算法。插入排序的原理和我们平时打牌的做法差不多。在开始摸牌的时候,我们的左手是空的,桌子上放着我们看不到数字的牌,接着一次次将新拿到的牌,放在左手(已经排好序)正确的位置,将新拿到的牌与左手中的牌从右到左(或者从左到右)进行比较,然后放到合适的位置,直到将桌子上的牌拿完。此时,我们左手中就是我们想要的按照想要的顺序的一个有序的集合啦。

 

伪代码实现

 

    那么通过上面的解释,使用伪代码表示应该是如下的形式:

    

 

//待排序的数组为A,key为需要比较的值

    for j = 2->length[A]

        do key = A[j]

              i = j - 1

        while(i > 0 && A[i] > key)

            do A[i+1] = A[i]

                 i = i - 1

        A[i+1] = key

 

 

确认算法正确性

 

    一般采用循环不变式帮助我们理解算法正确性。就是通过三个性质的成立性,来确保算法的正确性。分别是:初始化,保持,终止。简单的说明这是哪个性质就是:初始值成立,中间的谋个过程成立,结束的时候成立,就可以证明整个算法是没有问题的。这个过程与数学归纳法惊人的形似,想详细了解数学归纳法的话,可以看看这里(https://baike.so.com/doc/6143202.html)。

 

算法分析

 

    算法分析是指一个算法对计算机资源的消耗,一般从来个方面进行评估:时间复杂度和空间复杂度。一个好的算法会考虑当前环境下,怎么能达到最高的效率。当然,理想情况下,当时间复杂度和空间复杂度都小的情况下,达到效率最高。更多的情况下,会舍弃一种来达到我们想要的效果,这个需要根据具体情况来确定。

 

    一般情况下,我们对空间复杂度没有一个很好的度量标准来明确的表示出来,但是时间复杂度是可以比较清晰的表示出来,作为一个判断的标准。时间复杂度一般与输入的规模有关系,简单的理解就是就是输入元素个数。时间复杂度就是指,每一次运算所消耗的时间总和。

 

    还有一个比较重要的因素影响时间复杂度,那就是输入数据的情况。拿排序算法来说,如果输入的值本身就是排好序的还一个逆序的,这两种情况肯定是不一样的,显然一种是最佳情况,一种是最坏的情况。在设计一种算法时,应该最最佳情况、最坏情况还有平均情况有一定的了解,这样能更好的评估是否会使用这种算法。

 

插入排序算法实践(JS版)

 

    

 

var arr = [3,9,5,1,7,3]; //可以生成一些比较复杂的数据

 var key,j;

 console.time('time');

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

  key = arr[i];

  j = i - 1;

  while(j >= 0 && arr[j] > key) {

   arr[j+1] = arr[j];

   j--;

  }

  arr[j+1] = key;

 }

 console.timeEnd('time');

 console.log(arr);

 

 

代码交流 2021