首页 > 代码库 > 算法之插入排序
算法之插入排序
背景
当前存在排序的方法，这里以插入排序为例子，分析一个算法产生的过程。
问题描述
有这么一个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
确认算法正确性
一般采用循环不变式帮助我们理解算法正确性。就是通过三个性质的成立性，来确保算法的正确性。分别是：初始化，保持，终止。简单的说明这是哪个性质就是：初始值成立，中间的谋个过程成立，结束的时候成立，就可以证明整个算法是没有问题的。这个过程与数学归纳法惊人的形似，想详细了解数学归纳法的话，可以看看这里（http://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);
参考资料：《算法导论》
算法之插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。