冒泡排序

  • 原地排序
  • 稳定排序

  • 时间复杂度：O(n^2)

    1. function dubbleSort (arr) {
    2. for(let i = 0; i < arr.length; i++) {
    3.   let flag = false;
    4.   for(let j = 0; j < arr.length - i - 1; j++) {
    5.     if (arr[j] > arr[j+1]) {
    6.       const temp = arr[j+1];
    7.       arr[j+1] = arr[j];
    8.       arr[j] = temp;
    9.       flag = true;
    10.     }
    11.   }
    12.   if (!flag) break;
    13. }
    14. return arr;
    15. }

    选择排序

  • 原定排序

  • 不稳定排序

  • 时间复杂度：O(n^2)

    1. function selectionSort (arr) {
    2. let minIndex = 0;
    3. for(let i = 0; i < arr.length; i++) {
    4.   minIndex = i;
    5.   for(let j = i + 1; j < arr.length; j++) {
    6.     if (arr[j] < arr[minIndex]) {
    7.       minIndex = j;
    8.     }
    9.   }
    10.   const temp = arr[minIndex];
    11.   arr[minIndex] = arr[i];
    12.   arr[i] = temp;
    13. }
    14. return arr;
    15. }

    插入排序

  • 原地排序

  • 稳定排序

  • 时间复杂度：O(n^2)

    1. function insertionSort (arr) {
    2. for(let i = 1; i < arr.length; i++) {
    3.   let value = a[i];
    4.   let j = i - 1;
    5.   for(; j >= 0; j--) {
    6.     if (a[j] > value) {
    7.       a[j+1] = a[j];
    8.     }
    9.   }
    10.   a[j+1] = value;
    11. }
    12. }

    归并排序

  • 非原地排序

  • 稳定排序
  • 时间复杂度：O(nlog(n)) ```javascript const mergeSort = function(arr) { if (arr.length < 2) return arr; const midIndex = Math.floor(arr.length / 2); const left = arr.slice(0, midIndex); const right = arr.slice(midIndex, arr.length); return merge(mergeSort(left), mergeSort(right)); }

const merge = function(left, right) { const res = []; while(left.length && right.length) { if (left[0] <= right[0]) { res.push(left.shift()); } else { res.push(right.shift()); } } while(left.length) res.push(left.shift()); while(right.length) res.push(right.shift()); return res }

  1. <a name="yGrXN"></a>
  2. ## 快速排序
  4. - 原地排序
  5. - 非稳定排序
  6. - 时间复杂度：O(nlog(n))
  7. ```javascript
  8. const quickSort = function(arr) {
  9.   if (arr.length < 2) return arr;
  10.   const midIndex = Math.floor(arr.length / 2);
  11.   const mid = arr.splice(midIndex, 1)[0];
  12.   const left = [];
  13.   const right = [];
  14.   for(let i = 0; i < arr.length; i++) {
  15.     if (arr[i] < mid) {
  16.       left.push(arr[i]);
  17.     } else {
  18.       right.push(arr[i]);
  19.     }
  20.   }
  21.   return quickSort(left).concat([mid], quickSort(right));
  22. }