algorithmbook
algorithmbook copied to clipboard
链表排序
链表排序
最后我们看一下链表排序。排序时,我们不能使用任何访问link[index]的排序算法,因此有如下排序方法入围。
插入排序
将链表分明两部分,有序与未排序,每次从未排序区取得第一个,在有序区中找到适合位置进行插入
function insertSort(list) {
let head = list.head;
//如果没有或只有一个节点,直接返回
if (!head || !head.next){
return;
}
let lastSorted = head;//排好序的最后一个
while (lastSorted.next) {//如果还有下一个
let firstUnsort = lastSorted.next;//没有排好序的
if (lastSorted.val > firstUnsort.val) {
//排好序的最前一个
let firstSorted = head, prev = null
//将firstUnsort移除出来
lastSorted.next = firstUnsort.next
//求出firstUnsort的插入位置, 让它在有序区中逐一比较
while (firstSorted.val < firstUnsort.val) {
prev = firstSorted
firstSorted = firstSorted.next
}
if (!prev) {//如果firstUnsort是最小,那么prev为null,
//它将成为新的head, 并且旧的head充当它的next
firstUnsort.next = head
head = firstUnsort
} else {
prev.next = firstUnsort;
firstUnsort.next = firstSorted;
}
} else {
//firstUnsort刚好比lastSorted大
lastSorted = lastSorted.next;
}
}
//修正首尾节点
list.head = head;
list.tail = lastSorted
};
var list = new List()
var array = [2, 3, 8, 7, 4, 5, 9, 6, 1, 0]
array.forEach(function(el, i) {
list.insertAt(i, el)
})
list.forEach(function(el, i) {
console.log(i, el)
})
insertSort(list)
console.log("----sorted----", list)
list.forEach(function(el, i) {
console.log(i, el)
})
![image_1d7f24p6a17b9vbr1e18ctk1q3f9.png-22kB][11]
冒泡排序
左右结节进行比较交换,并且记录最后的结节,收窄比较的范围
function bubbleSort (list) {
var head = list.head
if (!head || !head.next) { // 只有一个或0个节点,不用排序
return
}
var smallest = new Node(Number.MIN_VALUE)
smallest.next = head;
list.tail = null; //准备重置tail
var len = 0, h = smallest;
while(h){
len++
h = h.next
}
for (var i = 0; i < len; i++) {//优化1
var hasSort = true
h = smallest
p1 = h.next
p2 = p1.next
for (var j = 0; j < len && p2; j++) {//优化2
if (p1.data > p2.data) {
h.next = p2
p1.next = p2.next
p2.next = p1
hasSort = false
}
h = h.next
p1 = h.next
p2 = p1.next
}
// 第一次冒泡结束后,p1的数据域最大,即为tail(p2已是null)
if (!list.tail) {
list.tail = p1
}
if (hasSort) {
break
}
}
// 重置新的head
list.head = smallest.next
}
我们可以回顾之前学到的冒泡优化,可以减少循环次数,如在优化1处,将i = 0
改成i = 1
;优化2处,则可以将j < len && p2
改成j < len - 1
。
我们还可以继续优化,引入swapPos变量,减少内循环次数。
function bubbleSort (list) {
//略....
var k = len - 1,swapPos = 0
for (var i = 1; i < len; i++) {
//略....
for (var j = 0; j < k; j++) {//k是可变的
if (p1.data > p2.data) {
//略....
hasSort = false
swapPos = j;
}
//略....
}
//略....
k = swapPos
}
// 重置新的head
list.head = smallest.next
}
选择排序
与插入排序一样,分为两个区,但它是每次从无序序区找到最小的节点,插入到有序区的最后
function selectSort (list) {
var head = list.head
if (!head || !head.next) {
return
}
var firstSorted, lastSorted, minPrev, min, p
while (head){
// 1. 在链表中找到数据域最小的节点。
for (p = head, min = head; p.next; p = p.next) {
if (p.next.val < min.val) {
minPrev = p
min = p.next
}
}
// 2. 构建有序链表
if (!firstSorted) {
firstSorted = min; // 如果目前还是一个空链表,那么设置 firstSorted
} else {
lastSorted.next = min; // 否则直接将min加在有序链表的末端
}
// 3. 调整lastSorted
lastSorted = min
// 4. 将min从原链表中移除
if (min == head) { // 如果找到的最小节点就是第一个节点
head = head.next; // 显然让head指向原head.next,即第二个节点,就OK
} else {
minPrev.next = min.next; // 移除
}
}
if (lastSorted) {
lastSorted.next = null; // 清空有序链表的最后节点的next引用
}
list.head = firstSorted
list.tail = lastSorted
}
快速排序
快排的核心是partition,我们选取第一个节点作为枢纽元,然后把小于枢纽的节点放到一个链中,把不小于枢纽的及节点放到另一个链中,最后把两条链以及枢纽连接成一条链。
function quickSort (list) {
var head = list.head
if (!head || !head.next) {
return
}
var tempHead = new Node(0)
tempHead.next = head
recursion(tempHead, head, null)
var h = list.head = tempHead.next
while(h){
list.tail = h
h = h.next
}
}
function recursion (prevHead, head, tail) {
// 链表范围是[low, high)
if (head != tail && head.next != tail) {
var mid = partition(prevHead, head, tail); // 注意这里head可能不再指向链表头了
recursion(prevHead, prevHead.next, mid)
recursion(mid, mid.next, tail)
}
}
function partition (prevLow, low, high) {
// 链表范围是[low, high)
var pivotkey = low.data; // low作为枢轴
var little = new Node('')
var bigger = new Node('')
var littleHead = little; // 保存原来的引用
var biggerHead = bigger; // 保存原来的引用
for (var node = low.next; node != high; node = node.next) {
if (node.data < pivotkey) {
little.next = node
little = node
} else {
bigger.next = node
bigger = node
}
}
// [ prevLow litterNode ... low biggerHead .... big, high ]
bigger.next = high
little.next = low
low.next = biggerHead.next; // 去掉biggerHead
prevLow.next = littleHead.next; // 去掉littleHead
return low
}
//======
function quicksort(head){
if(!head || !head.next){
return head;
}
var prevHead = new LinkNode(0)
prevHead.next = head
quicksort(prevHead, null)
return prevHead.next
}
function recursion(start, end){
if (start.next !== end){
var [prevPivot, pivot] = partition(start, end)
recursion(start, prevPivot)
recursion(pivot, end)
}
}
function partition(prevHead, end){//start一开始是tempHead, end为null
var second = prevHead.next.next;//第二个元素
var prevPivot = prevHead.next;//第一个元素
prevPivot.next = end //将第二个元素移出来
pivot = prevPivot;//prevPivot
//[prevHead, .... prevPivot, pivot, ....end]
while( second != end ){
var next = second.next
if (second.val >= prevPivot.val){
//如果第二个元素大于第一个元素,第一个元素为prevPivot
//那么将它发配到pivot的右侧
//pivot -> second-> pivot.next
second.next = pivot.next
pivot.next = second
if(second.val == prevPivot.val){
pivot = pivot.next
}
} else if (second.val < prevPivot.val){
//那么将它发配到prevPivot的左侧,prevHead的右侧
// prevHead -> second-> prevHead.next
second.next = prevHead.next
prevHead.next = second
}
second = next
}
return [prevPivot, pivot]
}
写得实在太好了!