本文示範 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
仔看 insertSort 的實作會發現兩個細節值得留意:一是每輪開始前先把 p.next 存進暫存變數,因為搬動節點後原本的位置資訊就失效了,需要靠它決定下一輪的起點;二是摘除與插入時,prev 與 next 兩側都要同步更新,否則雙向的鏈就斷了。中間那些逐步輸出的結果,正是每一輪插入後的中間狀態,拿來除錯很方便。希望本文所述對大家 JavaScript 程式設計有所幫助。