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

这篇文章主要介绍了javascript数据结构之双链表插入排序实现方法,较为详细的分析了插入排序的原理及双链表插入排序的实现技巧,对于学习JavaScript数据结构具有一定参考借鉴价值,需要的朋友可以参考下

本文实例讲述了javascript数据结构之双链表插入排序实现方法。分享给大家供大家参考，具体如下：

数组存储前提下，插入排序算法，在最坏情况下，前面的元素需要不断向后移，以便在插入点留出空位，让目标元素插入。

换成链表时，显然无需做这种大量移动，根据每个节点的前驱节点“指针”，向前找到插入点后，直接把目标值从原链表上摘下，然后在插入点把链表断成二截，然后跟目标点重新接起来即可。

1. <!doctype html> 
2. <html> 
3. <head> 
4. <title>双链表-插入排序</title> 
5. <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> 
6. </head> 
7. <script type="text/javascript"> 
8. //节点类 
9. var Node = function (pData) { 
10. this.next = null; //后继“指针” 
11. this.prev = null; //前驱"指针" 
12. this.data = pData; 
13. } 
14. //单链表(约定：头节点不放内容，当哨兵位，有效元素从头节点后的第1个元素开始) 
15. var DbLinkList = function () { 
16. this.head = new Node(null); //头节点  
17. //插入新元素 
18. this.insert = function (pNodeValue) { 
19. var newNode = new Node(pNodeValue); 
20. //如果只有头节点 
21. if (this.head.next == null) { 
22. this.head.next = newNode; 
23. newNode.prev = this.head; 
24. return; 
25. } 
26. //否则遍历找到尾节点 
27. var p = this.head; 
28. while (p.next != null) { 
29. p = p.next; 
30. } 
31. p.next = newNode; 
32. newNode.prev = p; 
33. } 
34. //获取第n个元素的数据值 
35. this.getData = function (index) { 
36. if (index < 1 || index > this.size) { 
37. return null; 
38. } 
39. var p = this.head; 
40. var i = 1; 
41. while (p.next != null && i <= index) { 
42. p = p.next; 
43. i += 1; 
44. } 
45. return p.data; 
46. } 
47. //取尾节点 
48. this.getTail = function () { 
49. if (this.head.next == null) { 
50. return null; 
51. } 
52. var p = this.head.next; 
53. while (p.next != null) { 
54. p = p.next; 
55. } 
56. return p; 
57. } 
58. //删除指定位置的元素 
59. this.removeAt = function (index) { 
60. if (index < 1 || index > this.size) { 
61. return null; 
62. } 
63. var p = this.head; 
64. var i = 1; 
65. //从头开始遍历，找到index位置的前一个元素 
66. while (p.next != null && i < index) { 
67. p = p.next; 
68. i += 1; 
69. } 
70. p.next = p.next.next; //修改index位置前一个元素的后继指针 
71. p.next.prev = p; 
72. return p.data; //返回删除元素的值  
73. } 
74. //打印所有元素 
75. this.print = function () { 
76. document.write("<br/>"); 
77. if (this.head.next == null) { 
78. return; 
79. } 
80. var p = this.head.next; 
81. while (p.next != null) { 
82. document.write(p.data + " "); 
83. p = p.next; 
84. } 
85. document.write(p.data + " "); //最后一个元素，需要单独打印 
86. document.write("<br/>"); 
87. } 
88. //从后打印所有元素 
89. this.printFromBack = function () { 
90. document.write("该链表共有" + this.size + "个元素，从后向前分别为:<br/>"); 
91. var tail = this.getTail(); 
92. var p = tail; 
93. if (p == null) { 
94. return; 
95. } 
96. while (p.prev != null) { 
97. document.write(p.data + " "); 
98. p = p.prev; 
99. } 
100. document.write("<br/>"); 
101. } 
102. //插入排序 
103. this.insertSort = function () { 
104. if (this.head.next == null || this.head.next.next == null) { 
105. return; 
106. } 
107. var p = this.head.next; 
108. while (true) { 
109. if (p == null) { 
110. return; 
111. } 
112. var t = p.prev; 
113. //向前查找p之前的插入点 
114. while (t.prev != null && t.data > p.data) { 
115. t = t.prev; 
116. } 
117. //如果插入点就是p的前驱节点，不用调整， 
118. //忽略，直接进入下一轮 
119. if (t.next == p) { 
120. p = p.next; 
121. continue; 
122. } 
123. //将p的后续节点先保护起来，以便下一轮循环时确定起始位置 
124. var x = p.next; 
125. //将p从链表上摘下 
126. if (p.next != null) { 
127. p.next.prev = p.prev; 
128. } 
129. p.prev.next = p.next; 
130. //p插入到t之后 
131. t.next.prev = p; 
132. p.next = t.next; 
133. t.next = p; 
134. p.prev = t; 
135. this.print(); //打印输出，调试用  
136. //重新将p定位到下一轮循环的"正确"起始节点 
137. p = x; 
138. } 
139. } 
140. } 
141. var linkTest = new DbLinkList(); 
142. linkTest.insert(10); 
143. linkTest.insert(9); 
144. linkTest.insert(8); 
145. linkTest.insert(7); 
146. linkTest.insert(6); 
147. linkTest.insert(5); 
148. linkTest.insert(4); 
149. linkTest.insert(3); 
150. linkTest.insert(2); 
151. linkTest.insert(1); 
152. document.write("--排序前---<br/>") 
153. linkTest.print(); 
154. linkTest.insertSort(); 
155. document.write("<br/>--排序后---<br/>") 
156. linkTest.print(); 
157. </script> 
158. </html> 

运行结果如下：

1. --排序前--- 
2.  
3. 10 9 8 7 6 5 4 3 2 1  
4.  
5. 9 10 8 7 6 5 4 3 2 1  
6.  
7. 8 9 10 7 6 5 4 3 2 1  
8.  
9. 7 8 9 10 6 5 4 3 2 1  
10.  
11. 6 7 8 9 10 5 4 3 2 1  
12.  
13. 5 6 7 8 9 10 4 3 2 1  
14.  
15. 4 5 6 7 8 9 10 3 2 1  
16.  
17. 3 4 5 6 7 8 9 10 2 1  
18.  
19. 2 3 4 5 6 7 8 9 10 1  
20.  
21. 1 2 3 4 5 6 7 8 9 10  
22.  
23. --排序后--- 
24.  
25. 1 2 3 4 5 6 7 8 9 10 

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