链表排序

最后我们看一下链表排序。排序时，我们不能使用任何访问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]
}

RubyLouvre / algorithmbook

链表排序 #23

链表排序

插入排序

冒泡排序

选择排序

快速排序