javascript:ダブルリンク表-挿入ソート
5588 ワード
配列記憶の前提の下で、並べ替えアルゴリズムを挿入します.最悪の場合、前の要素は挿入点に空きスペースを残して、ターゲット要素を挿入します.
チェーンに換える時、このような大量移動をする必要はないことは明らかです.各ノードの前駆ノードの「ポインタ」によって、前に挿入点を見つけたら、直接にターゲット値を元のチェーンから外して、挿入点でチェーンを二つに切って、目標点と再び接続すればいいです.
チェーンに換える時、このような大量移動をする必要はないことは明らかです.各ノードの前駆ノードの「ポインタ」によって、前に挿入点を見つけたら、直接にターゲット値を元のチェーンから外して、挿入点でチェーンを二つに切って、目標点と再び接続すればいいです.
<!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>