数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。
换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点“指针”,向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可。
输出,调试用
//重新将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("--排序前---
") linkTest.print(); linkTest.insertSort(); document.write("
--排序后---
") linkTest.print(); script>
") linkTest.print(); linkTest.insertSort(); document.write("
--排序后---
") linkTest.print(); script>