编辑代码

let arr = [5, 3, 1, 9, 6, 4, 2, 8, 7];

// 冒泡排序
const bubbleSort = (arr: number[]): void => {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (arr[i] <= arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        console.log(`i=${i},j=${j},\n${arr}`);
      }
    }
  }
}

// 选择排序：依次从待排序数组序列中选出最小（最大）的数字放在已排序序列的最前面
const selectionSort = (arr: number[]): void => {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let minLength = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minLength]) {
        minLength = j;
      }
    }
    if (minLength !== i) {
      [arr[i], arr[minLength]] = [arr[minLength], arr[i]];
    }
  }
}

// 插入排序：依次从待排序数组序列中取出数字，放到已排序序列的正确位置
const insertionSort = (arr: number[]): void => {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    const current = arr[i];
    let j = i - 1;
    for (; j >= 0; j--) {
      if (current < arr[j]) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = current;
  }
}

// 快速排序1：递归+拆分新数组
const quickSort1 = (arr: number[]): number[] => {
  if (!arr.length) {
    return arr;
  }
  const pivotIndex = Math.floor(Math.random() * arr.length);
  const pivot = arr[pivotIndex];
  const ltArr = arr.filter(n => n < pivot);
  const eqArr = arr.filter(n => n === pivot);
  const gtArr = arr.filter(n => n > pivot);
  
  return [...quickSort1(ltArr), ...eqArr, ...quickSort1(gtArr)];
}

// 处理分区并返回基准下标
const partition = (arr: number[], start: number, end: number): number => {
  const pivot = arr[end];
  let i = start;
  for (let j = i; j < end; j++) {
    if (arr[j] <= pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[end]] = [arr[end], arr[i]];
  return i;
};

// 快速排序2：递归+原址
const quickSort2 = (arr: number[], start: number, end: number) => {
  if (!arr.length || start > end) {
    return arr;
  }
  const nextPivotIndex = partition(arr, start, end);
  
  quickSort2(arr, start, nextPivotIndex - 1);
  quickSort2(arr, nextPivotIndex + 1, end);
};

// 快速排序3：非递归+原址
const quickSort3 = (arr: number[]) => {
  if (!arr.length) {
    return arr;
  }
  const stack: number[] = [];
  stack.push(0);
  stack.push(arr.length - 1);
  
  while (stack.length) {
    const end = stack.pop() || 0;
    const start = stack.pop() || 0;
    
    const nextPivotIndex = partition(arr, start, end);
    if (nextPivotIndex - 1 > start) {
      stack.push(start);
      stack.push(nextPivotIndex - 1)
    }
    if (nextPivotIndex + 1 < end) {
      stack.push(nextPivotIndex + 1);
      stack.push(end);
    }
  }
}

// 归并算法
const mergeSort = (arr: number[]): number[] => {
  if (!arr.length || arr.length === 1) {
    return arr;
  }
  
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
  
  const sorted: number[] = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < sortedLeft.length && rightIndex < sortedRight.length) {
    if (sortedLeft[leftIndex] <= sortedRight[rightIndex]) {
      sorted.push(sortedLeft[leftIndex]);
      leftIndex++;
    } else {
      sorted.push(sortedRight[rightIndex]);
      rightIndex++;
    }
  }
  while (leftIndex < sortedLeft.length) {
    sorted.push(sortedLeft[leftIndex]);
    leftIndex++;
  }
  while (rightIndex < sortedRight.length) {
    sorted.push(sortedRight[rightIndex]);
    rightIndex++;
  }
  return sorted;
}

const mergeSort2 = (arr: number[]): number[] => {
  if (!arr.length || arr.length === 1) {
    return arr;
  }
  
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
  
  const sorted: number[] = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (sortedLeft.length && sortedRight.length) {
    const topLeft: number | undefined = sortedLeft.shift();
    if (topLeft === undefined) break;
    const topRight: number | undefined = sortedRight.shift();
    if (topRight === undefined) break;
    if (topLeft <= topRight) {
      sorted.push(topLeft);
      sortedRight.unshift(topRight);
    } else {
      sorted.push(topRight);
      sortedLeft.unshift(topLeft);
    }
  }
  
  sorted.push(...sortedLeft);
  sorted.push(...sortedRight);
  
  return sorted;
}

// console.log(`排序前：${arr}`)
// bubbleSort(arr);
// selectionSort(arr);
// insertionSort(arr);
// arr = quickSort1(arr);
// quickSort2(arr, 0, arr.length - 1);
// quickSort3(arr)
// const sortedArr = mergeSort2(arr);

// console.log(`排序后：${sortedArr}`);

interface ListNode {
  value: number;
  next: ListNode | null;
}

const getPrintListNodeStr = (node: ListNode | null) => {
  if (!node) {
    return '';
  }
  const result = [node.value];
  let next = node.next;
  while (next) {
    result.push(next.value);
    next = next.next;
  }
  return result.join(' => ');
}

const head: ListNode = {
  value: 5,
  next: {
    value: 3,
    next: {
      value: 1,
      next: {
        value: 9,
        next: {
          value: 6,
          next: {
            value: 4,
            next: {
              value: 2,
              next: {
                value: 8,
                next: {
                  value: 7,
                  next: null,
                }
              }
            }
          }
        }
      }
    }
  },
};

const bubbleSortList = (head: ListNode | null): ListNode | null => {
  if (!head || !head.next) {
    return head;
  }
  
  let current1: ListNode | null = head;
  while (current1) {
    let current2: ListNode | null = head;
    while (current2) {
      if (current1.value < current2.value) {
        const temp1: number = current1.value;
        const temp2: number = current2.value;
        current1.value = temp2;
        current2.value = temp1;
      }
      current2 = current2.next;
    }
    current1 = current1.next;
  }
  return head;
}

const insertionSortList = (head: ListNode | null): ListNode | null => {
  if (!head || !head.next) {
    return head;
  }
  
  let current: ListNode | null = head.next;
  let sorted: ListNode | null = head;
  sorted.next = null;
  
  while (current) {
    let prev: ListNode | null = null;
    let currentSorted: ListNode | null = sorted;
    while (currentSorted) {
      if (current.value < currentSorted.value) {
        break;
      }
      prev = currentSorted;
      currentSorted = currentSorted.next;
    }
    
    const temp = current;
    current = current.next;
    temp.next = currentSorted;
    
    if (prev) {
      prev.next = temp;
    } else {
      sorted = temp;
    }
  }
  return sorted;
}

// 使用选择排序，对链表进行从小到大的排序
const selectionSortList = (head: ListNode | null): ListNode | null => {
  if (!head || !head.next) {
    return head;
  }
  // 待排序节点
  let current: ListNode | null = head;
  // 已排序链表
  let sorted: ListNode | null = null;
  
  while (current) {
    console.log(`current: ${getPrintListNodeStr(current)};sorted: ${getPrintListNodeStr(sorted)}`);
    // 当次循环最小值的前节点
    let prev: ListNode | null = null;
    // 当次循环的临时前节点
    let tempPrev: ListNode | null = current;
    // 当次循环找到的最小值节点
    let minNode: ListNode | null = current;
    // 待排序节点
    let penddingNode: ListNode | null = current.next;
    while (penddingNode) {
      // 如果待排序节点的值小于当前记录的最小节点的值，则最小节点更换为待排序节点
      if (penddingNode.value > minNode.value) {
        minNode = penddingNode;
        prev = tempPrev; // 记录当前最小节点的前节点
      }
      // 记录临时前节点
      tempPrev = penddingNode;
      // 继续检查下一个节点
      penddingNode = penddingNode.next;
    }
    
    
    // 将current指向下一个 && 将待排序链表中最小值删除，以便下次循环
    if (prev) {
      prev.next = minNode.next;
    } else {
      current = minNode.next;
    }
    // 将已排序链表的头结点指向当次循环最小值节点
    minNode.next = sorted;
    sorted = minNode;
    
  }
  
  return sorted;
}

// 归并排序
const mergeSortList = (head: ListNode | null): ListNode | null => {
  if (!head || !head.next) {
    return head;
  }
  
  // 快慢指针法获取中间节点
  let middle: ListNode | null = getMiddle(head);
  
  const middleNext = middle!.next;
  middle!.next = null;
  
  let left: ListNode | null = mergeSortList(head);
  let right: ListNode | null = mergeSortList(middleNext);
  
  
  let temp: ListNode = { value: 0, next: null };
  let current: ListNode | null = temp;
  
  while(left && right) {
    if (left!.value <= right!.value) {
      current!.next = left;
      left = left!.next;
    } else {
      current!.next = right;
      right = right!.next;
    }
    current = current!.next;
  }
  // 处理剩下的
  current!.next = left || right;
  
  return temp.next!;
}

const getMiddle = (head: ListNode | null): ListNode | null => {
  if (!head || !head.next || !head.next!.next) {
    return head;
  }
  // 快慢指针法获取中间节点
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while(fast && fast.next) {
    slow = slow!.next;
    fast = fast!.next!.next;
  }
  return slow;
}


console.log(`排序前链表：${getPrintListNodeStr(head)}`)
// const sortedHead = bubbleSortList(head);
// const sortedHead = insertionSortList(head);
// const sortedHead = selectionSortList(head);
try {
  const sortedHead = mergeSortList(head);
  console.log(`排序后链表：${getPrintListNodeStr(sortedHead)}`)
} catch (e) {
  console.log(e);
}