js实现无序链表排序

实现无序链表排序的方法

在JavaScript中，可以使用多种方法对无序链表进行排序。以下是几种常见的实现方式，包括冒泡排序、归并排序和快速排序。

冒泡排序实现链表排序

冒泡排序是一种简单的排序算法，适用于链表结构。通过多次遍历链表，比较相邻节点的值并交换它们的位置，直到链表完全有序。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function bubbleSortLinkedList(head) {
  if (!head || !head.next) return head;

  let swapped;
  do {
    swapped = false;
    let current = head;
    let prev = null;

    while (current && current.next) {
      if (current.value > current.next.value) {
        // 交换节点值
        const temp = current.value;
        current.value = current.next.value;
        current.next.value = temp;
        swapped = true;
      }
      prev = current;
      current = current.next;
    }
  } while (swapped);

  return head;
}

归并排序实现链表排序

归并排序是一种分治算法，适用于链表排序。通过递归地将链表分成两部分，分别排序后再合并。

function mergeSortLinkedList(head) {
  if (!head || !head.next) return head;

  // 使用快慢指针找到链表中点
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  const mid = slow.next;
  slow.next = null;

  const left = mergeSortLinkedList(head);
  const right = mergeSortLinkedList(mid);

  return merge(left, right);
}

function merge(left, right) {
  const dummy = new Node(0);
  let tail = dummy;

  while (left && right) {
    if (left.value < right.value) {
      tail.next = left;
      left = left.next;
    } else {
      tail.next = right;
      right = right.next;
    }
    tail = tail.next;
  }

  tail.next = left || right;
  return dummy.next;
}

快速排序实现链表排序

快速排序通过选择一个基准值将链表分成两部分，递归地对两部分进行排序。

function quickSortLinkedList(head) {
  if (!head || !head.next) return head;

  const pivot = head.value;
  let less = new Node(0);
  let equal = new Node(0);
  let greater = new Node(0);
  let lessTail = less;
  let equalTail = equal;
  let greaterTail = greater;
  let current = head;

  while (current) {
    if (current.value < pivot) {
      lessTail.next = current;
      lessTail = lessTail.next;
    } else if (current.value === pivot) {
      equalTail.next = current;
      equalTail = equalTail.next;
    } else {
      greaterTail.next = current;
      greaterTail = greaterTail.next;
    }
    current = current.next;
  }

  lessTail.next = equalTail.next = greaterTail.next = null;

  less = quickSortLinkedList(less.next);
  greater = quickSortLinkedList(greater.next);

  equalTail.next = greater;
  if (!less) return equal.next;

  let lessTailFinal = less;
  while (lessTailFinal.next) {
    lessTailFinal = lessTailFinal.next;
  }
  lessTailFinal.next = equal.next;
  return less;
}

选择排序实现链表排序

选择排序通过每次选择未排序部分的最小值，将其放到已排序部分的末尾。

function selectionSortLinkedList(head) {
  if (!head || !head.next) return head;

  let current = head;
  while (current) {
    let minNode = current;
    let temp = current.next;

    while (temp) {
      if (temp.value < minNode.value) {
        minNode = temp;
      }
      temp = temp.next;
    }

    // 交换节点值
    const tempValue = current.value;
    current.value = minNode.value;
    minNode.value = tempValue;

    current = current.next;
  }

  return head;
}

插入排序实现链表排序

插入排序通过构建有序链表，逐个将未排序的节点插入到有序链表中。

function insertionSortLinkedList(head) {
  if (!head || !head.next) return head;

  const dummy = new Node(0);
  dummy.next = head;
  let lastSorted = head;
  let current = head.next;

  while (current) {
    if (lastSorted.value <= current.value) {
      lastSorted = lastSorted.next;
    } else {
      let prev = dummy;
      while (prev.next.value <= current.value) {
        prev = prev.next;
      }
      lastSorted.next = current.next;
      current.next = prev.next;
      prev.next = current;
    }
    current = lastSorted.next;
  }

  return dummy.next;
}

以上方法可以根据实际需求选择使用，归并排序和快速排序通常效率更高，适合处理较大的链表。