Tag: 排序算法

本文主要介绍常见的 5 种排序算法：冒泡排序，选择排序，插入排序，快速排序，归并排序。

---

冒泡排序

function bubbleSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = 0; j < array.length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
    console.log(array);
  }

  return array;
}

---

参考：

https://learn.freecodecamp.org/coding-interview-prep/algorithms/implement-bubble-sort

https://guide.freecodecamp.org/certifications/coding-interview-prep/algorithms/implement-bubble-sort/

选择排序

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[i]) {
        [array[i], array[j]] = [array[j], array[i]];
      }
    }
    console.log(array);
  }
  
  return array;
}

---

参考：

https://learn.freecodecamp.org/coding-interview-prep/algorithms/implement-selection-sort

https://guide.freecodecamp.org/certifications/coding-interview-prep/algorithms/implement-selection-sort/

插入排序

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let curr = array[i];
    for (let j = i - 1; j >= 0; j--) {
      if (array[j] > curr) {
        array[j + 1] = array[j];
      } else {
        array[j + 1] = curr;
        break;
      }
    }
    console.log(array);
  }

  return array;
}

---

参考：

https://learn.freecodecamp.org/coding-interview-prep/algorithms/implement-insertion-sort

https://guide.freecodecamp.org/certifications/coding-interview-prep/algorithms/implement-insertion-sort/

快速排序

function quickSort(array, left = 0, right = array.length - 1) {
  if (left < right) {
    let pivot = left;
    let pivotValue = array[left];

    for (let i = left + 1; i <= right; i++) {
      if (array[i] < pivotValue) {
        pivot++;
        [array[i], array[pivot]] = [array[pivot], array[i]];
      }
    }

    [array[left], array[pivot]] = [array[pivot], array[left]];

    quickSort(array, left, pivot - 1);
    quickSort(array, pivot + 1, right);
  }
  
  console.log(array);
  
  return array;
}

---

参考：

https://learn.freecodecamp.org/coding-interview-prep/algorithms/implement-quick-sort

https://guide.freecodecamp.org/certifications/coding-interview-prep/algorithms/implement-quick-sort/

归并排序

function mergeSort(array) {
  if (array.length > 1) {
    let array1 = array.slice(0, array.length / 2);
    let array2 = array.slice(array.length / 2, array.length);

    console.log(array1, array2);

    return merge(mergeSort(array1), mergeSort(array2));
  } else {
    return array;
  }
}

function merge(array1, array2) {
  let [i, j] = [0, 0];
  let array = [];

  while (i + j < array1.length + array2.length) {
    if ((array1[i] < array2[j] && i < array1.length) || j == array2.length) {
      array[i + j] = array1[i];
      i++;
    } else {
      array[i + j] = array2[j];
      j++;
    }
  }

  console.log(array);

  return array;
}

---

参考：

https://learn.freecodecamp.org/coding-interview-prep/algorithms/implement-merge-sort

https://guide.freecodecamp.org/certifications/coding-interview-prep/algorithms/implement-merge-sort/

 649 total views