JS插入排序简单理解与实现方法分析
本文实例讲述了JS插入排序简单理解与实现方法。分享给大家供大家参考，具体如下：
在这里，我详细的讲一下我个人对于插入排序的理解。
每个人对于事物的理解都是不一样的，因为每个人对世界万物的看法和思考方式都不一样。因此，对于排序算法，我想每个人都有自己的理解方式，所以，虽然博客园里有很多关于排序的文章，但那只是其他人对这几个排序的理解方式，而笔者也有自己的理解方式，所以，笔者也就没有在意博客园写了那么多关于排序的文章而还在这里写下个人的见解了。
对于插入排序，笔者是这么理解的：
插入排序就是把一组数字分成两部分，一部分是排好顺序的，另一部分是没有排好顺序的，然后，就是从没有排好顺序的那组数字中获取数字，把它插入到已经排好的顺序的那部分数字中，当然，在插入到已经排好顺序的那部分数字时，你还必须让这个插入进来的数字与已经排好顺序的数字进行比较，为的是保证已经排好的顺序的那部分数字不被打乱，插入排序的关键也就是这里，如果能够理解这里，我想对于接下来我写的代码应该不难理解了。
我举个例子：
这是个杂乱的一组数字：8,1,2,5,9,3,4,6,7,0
看到上面的那组数字吗？你觉得能把这组数字分出一部分有序的出来吗？因为，我们插入排序首先要做的就是在一组数字中找出有序的部分，所以，首先，你得从一组数字中找到有序的才行对吧？其实，上面那组数字是可以找到有序的部分的。怎么说呢？很简单，你把第一个数字8当成一部分，其余的当成另外一部分，不就分出一部分有序的数字和一部分无序的数字了吗？你想想，第一部分就是一个数字8，一个数字构成的一部分，它都不用比较了，这还不是有序的那还得了，呵呵。
之所以在这里提一下一个数字当成一部分的情况，那是因为，我们所提供的插入排序的数字是杂乱的，无序的，我们谁也不能保证最开始的那部分一定是有序的，因此，我们就只能选择一个数字作为有序的那部分才能保证所有的排序都是在有序那部分进行的，不然，插入排序就没办法找到有序的那部分了。
插入排序开始：
第一个有序部分（就是第一个数字了）：8
第一个无序部分（就是剩下的部分了）：1,2,5,9,3,4,6,7,0
根据前面所讲的插入排序原理：从无序部分中获取数字，把它插入到有序的那一部分中。
1、这里怎么在无序部分中获取数字？
2、怎么把获取的数字有序的插入到有序部分中？换句话说，就是怎么让这个获取的数字插入到有序的那部分之后，有序的那部分还是有序的，并不会被这个插入的数字破坏掉队形而变得无序？
首先回答第一个问题：
这个问题其实很简单啦，我们把那组无序的数组分成两部分之后，只要从无序的那部分数字的第一个数字开始往后面获取数字就行了，是吧？
接下来回答第二个问题：
这个问题有点复杂，我就不叙述了，直接举例子吧，这样子更容易理解。
第二次插入排序：
首先我们从上面已经分好的无序部分：1,2,5,9,3,4,6,7,0（前面已经把8分成有序的部分了）获取第一个数字1，假设我们是从小排到大的排序这组数字，获取1这个数字之后，我们就要把1插入到8中啦，对吧？
我们把1和8做比较，比较规则：大于，8>1？真，既然是真，那么它们就要调换位置了，对吧？
所以经过一次排序之后，原来的那组有序数字和无序数字就变成了下面的了：
第二个有序部分：1,8
第二个无序部分：2,5,9,3,4,6,7,0
经过两轮的有序和无序分组之后，就得到上面的两个有序数字和无序数字了，接下来，我们继续插入排序
依然从后面的无序部分获取数字2，获取之后，从有序部分的后面数字开始逐一的和2做比较，8>2吗？真，那么它们两者就调换位置。接下来让1和2作比较，1>2吗？假，那么就跳过不管，所以，就得到下面的有序和无序部分了。
第三个有序部分：1,2,8
第三个无序部分：5,9,3,4,6,7,0
比较到这里，插入排序已经初步形成有序数字了，接下来的比较我就不叙述了，你们自己想想吧。接下来是代码，代码的思维和这里的描述是一样的，你可以自己调试看一下代码的执行过程就再明白不过了。
注意、每一轮比较过后，有序部分总会多一个元素，而无序部分则少一个元素，插入排序嘛，就是从无序部分截取数字插入到有序部分中啦，这和下面的代码循环是一致的。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-cn">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
<title>js的插入排序</title>
<meta name="keywords" content="关键字列表" />
<meta name="description" content="网页描述" />
<link rel="stylesheet" type="text/css" href="" />
<style type="text/css"></style>
<script type="text/javascript">
//插入排序，参数是数组
function insertSort(arr){
//判断参数的合法性
if(toString.call(arr) !== '[object Array]'){
return false;
}
//获取数组的长度
var len = arr.length;
if(len <= 1){
return arr;//小于等于1不用排序
}
//i=1开始，留着0作为有序部分，也就是说，外层循环获取数组后面的元素，也就是上面所讲的无序部分
for(var i=1;i<len;i++){
//j=i-1，就是获取有序部分最后的一个元素作为对照，也就是有序部分
for(var j=i-1;j>=0;j--){//注意，j--,就是从有序部分的后面元素开始和无序部分的元素作比较
if(arr[j] > arr[j+1]){//第一个j+1也就是外层循环i，
//互换元素，对前面数组进行排序
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
//测试
var ar = [9,3,8,5,2,7,0,6,1,4];
alert(insertSort(ar));
</script>
</head>
<body>
</body>
</html>
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。
PS：这里再为大家推荐一款关于排序的演示工具供大家参考：
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
相关推荐
-
JS实现的冒泡排序，快速排序，插入排序算法示例
本文实例讲述了JS实现的冒泡排序,快速排序,插入排序算法.分享给大家供大家参考,具体如下: 一.冒泡排序 大致分两步: 1.依次对比相邻2个数字,前者比后者大就调换位置 2.重复第一步操作,直到所有数字都按顺序排列 function bubbleSort(arr){ for(var i=1; i<arr.length; i++){ for(var j=0; j<arr.length-i; j++){ if(arr[j]>arr[j+1]){ arr[j]=[arr[j+1],arr[j+
-
JavaScript实现链表插入排序和链表归并排序
本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序,链表的归并排序就是对每个部分都进行归并排序,然后合并在一起. 1.链表 1.1链表的存储表示 //链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 1.2基本操作 创建链表: /* * 创建链表. * 形参num为链表的长度,函数返回链表的头指针. */ Link
-
JS折半插入排序算法实例
本文实例讲述了JS折半插入排序算法.分享给大家供大家参考,具体如下: function pushArrayWithIndex(arr, index, value) { // 将元素添加到数组的指定位置 var temArr = arr.slice(0, index); temArr.push(value); return temArr.concat(arr.slice(index)); } /* test for pushArrayWithIndex var arr = [1, 2, 3, 4,
-
JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】
本文实例讲述了JavaScript数据结构与算法之基本排序算法定义与效率比较.分享给大家供大家参考,具体如下: javascript数据结构与算法--基本排序算法(冒泡.选择.排序)及效率比较 一.数组测试平台 javascript数据结构与算法--基本排序(封装基本数组的操作),封装常规数组操作的函数,比如:插入新数据,显示数组数据,还有交换数组元素等操作来调用不同的排序算法 function CArray(numElements) { this.dataStore = []; this.po
-
JS实现冒泡排序，插入排序和快速排序并排序输出
在一次面试中被问到了此问题,但是真是懵了,没能回答上来,后来通过JS整理了一下,在结合html代码做了一个文本框,把输入的内容从文本框排序输出,再次不做叙述了,下面通过一段代码给大家展示下: 以下是代码: index.html <!DOCTYPE html> <html> <head> <title>Sorting</title> <link rel="stylesheet" type="text/css&qu
-
JavaScript实现经典排序算法之插入排序
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂.像排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下.然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置.为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌. 1)算法原理 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序
-
JavaScript插入排序算法原理与实现方法示例
本文实例讲述了JavaScript插入排序算法原理与实现方法.分享给大家供大家参考,具体如下: 一.插入排序简介: 想象我们斗地主,摸排阶段,手里的牌都按照从小到大排序.如果每摸一张牌,我们就把他插入合适的位置,使得它比后面位置的牌小,比前面位置的牌大或者相等. 类似这样的一种排序方法就是插入排序: 在一个数组a中,我们要实现升序排序,假设我们前面已经对a[0]到a[k]排好序,现在需要将a[k+1]的值放入合适的位置. (为简便,此处不讨论k的取值范围,只是用它代表数组的某个位置) 1.首先,
-
JS排序算法之冒泡排序，选择排序与插入排序实例分析
本文实例讲述了JS排序算法之冒泡排序,选择排序与插入排序.分享给大家供大家参考,具体如下: 冒泡排序: 对数组的中的数据,依次比较相邻两数的大小. 如果前面的数据大于后面的数据,就交换这两个数. 时间复杂度O(n^2) function bubble(array){ var temp; for(var i=0; i<arr.length; i++){ for(var j=0; j<arr.length; j++){ if(arr[j]>arr[j+1]){ temp = arr[j+1]
-
js排序动画模拟-插入排序
0 && (t > 0; } //--> [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]
-
基于JavaScript实现的插入排序算法分析
本文实例讲述了基于JavaScript实现的插入排序算法.分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序. 内部排序是指待排序记录存放在计算机随机存储器中进行的排序过程:外部排序指的是待排序的记录数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程. 下面介绍几种常见的内部排序方式: 插入排序 插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入已排好序的有序表中,从而得到一个新的.记录数加1的有
-
javascript算法学习(直接插入排序)
1.基本思想 假设待排序的记录存放在数组R[1..n]中.初始时,R[1]自成1个有序区,无序区为R[2..n].从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区. 复制代码 代码如下: <!doctype html> <html> <head><title>javascript直接插入排序</title> <meta charset = "utf-8" /> &
-
javascript数据结构之双链表插入排序实例详解
本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t