本文主要介绍常见的 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
选择排序
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
插入排序
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
快速排序
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