javascript数据结构之双链表插入排序实例详解

本文实例讲述了javascript数据结构之双链表插入排序实现方法。分享给大家供大家参考，具体如下：
数组存储前提下，插入排序算法，在最坏情况下，前面的元素需要不断向后移，以便在插入点留出空位，让目标元素插入。
换成链表时，显然无需做这种大量移动，根据每个节点的前驱节点“指针”，向前找到插入点后，直接把目标值从原链表上摘下，然后在插入点把链表断成二截，然后跟目标点重新接起来即可。

<！doctype html><html><head><title>双链表-插入排序</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /></head><script type="text/javascript">//节点类var Node = function （pData） {this.next = null; //后继“指针”this.prev = null; //前驱"指针"this.data = pData;}//单链表（约定：头节点不放内容，当哨兵位，有效元素从头节点后的第1个元素开始）var DbLinkList = function （） {this.head = new Node（null）; //头节点 //插入新元素this.insert = function （pNodeValue） {var newNode = new Node（pNodeValue）;//如果只有头节点if （this.head.next == null） {this.head.next = newNode;newNode.prev = this.head;return;}//否则遍历找到尾节点var p = this.head;while （p.next ！= null） {p = p.next;}p.next = newNode;newNode.prev = p;}//获取第n个元素的数据值this.getData = function （index） {if （index < 1 || index > this.size） {return null;}var p = this.head;var i = 1;while （p.next ！= null && i <= index） {p = p.next;i += 1;}return p.data;}//取尾节点this.getTail = function （） {if （this.head.next == null） {return null;}var p = this.head.next;while （p.next ！= null） {p = p.next;}return p;}//删除指定位置的元素this.removeAt = function （index） {if （index < 1 || index > this.size） {return null;}var p = this.head;var i = 1;//从头开始遍历，找到index位置的前一个元素while （p.next ！= null && i < index） {p = p.next;i += 1;}p.next = p.next.next; //修改index位置前一个元素的后继指针p.next.prev = p;return p.data; //返回删除元素的值}//打印所有元素this.print = function （） {document.write（"<br/>"）;if （this.head.next == null） {return;}var p = this.head.next;while （p.next ！= null） {document.write（p.data + " "）;p = p.next;}document.write（p.data + " "）; //最后一个元素，需要单独打印document.write（"<br/>"）;}//从后打印所有元素this.printFromBack = function （） {document.write（"该链表共有" + this.size + "个元素，从后向前分别为:<br/>"）;var tail = this.getTail（）;var p = tail;if （p == null） {return;}while （p.prev ！= null） {document.write（p.data + " "）;p = p.prev;}document.write（"<br/>"）;}//插入排序this.insertSort = function （） {if （this.head.next == null || this.head.next.next == null） {return;}var p = this.head.next;while （true） {if （p == null） {return;}var t = p.prev;//向前查找p之前的插入点while （t.prev ！= null && t.data > p.data） {t = t.prev;}//如果插入点就是p的前驱节点，不用调整，//忽略，直接进入下一轮if （t.next == p） {p = p.next;continue;}//将p的后续节点先保护起来，以便下一轮循环时确定起始位置var x = p.next;//将p从链表上摘下if （p.next ！= null） {p.next.prev = p.prev;}p.prev.next = p.next;//p插入到t之后t.next.prev = p;p.next = t.next;t.next = p;p.prev = t;this.print（）; //打印输出，调试用//重新将p定位到下一轮循环的"正确"起始节点p = x;}}}var linkTest = new DbLinkList（）;linkTest.insert（10）;linkTest.insert（9）;linkTest.insert（8）;linkTest.insert（7）;linkTest.insert（6）;linkTest.insert（5）;linkTest.insert（4）;linkTest.insert（3）;linkTest.insert（2）;linkTest.insert（1）;document.write（"--排序前---<br/>"）linkTest.print（）;linkTest.insertSort（）;document.write（"<br/>--排序后---<br/>"）linkTest.print（）;</script></html>

运行结果如下：

 --排序前---10 9 8 7 6 5 4 3 2 1 9 10 8 7 6 5 4 3 2 1 8 9 10 7 6 5 4 3 2 1 7 8 9 10 6 5 4 3 2 1 6 7 8 9 10 5 4 3 2 1 5 6 7 8 9 10 4 3 2 1 4 5 6 7 8 9 10 3 2 1 3 4 5 6 7 8 9 10 2 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 --排序后---1 2 3 4 5 6 7 8 9 10

希望本文所述对大家JavaScript程序设计有所帮助。