【JS算法】几种排序算法

冒泡排序

从第一个人开始，每个人和右边人比较，如果你比他高，就交换位置，否则就不动。
这是简单粗暴的解发，时间复杂度是n^2 若数组长100,那就会执行100*100=1万次。

const arr = [9, 6, 3, 15, 5, 7, 16, 4, 2, 13, 14];
function sort(arr) {
  let len = arr.length - 1;
  for (let j = 0; j < len; j++) {
    //第二个循环，每次从0开始
    for (let i = 0; i < len - j; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
      }
    }
  }
  return arr;
}
const res = sort(arr);
console.log(res);

---

根据二分逻辑的快排算法

给数组找一个标志位，比如我，所有人都与我比个头，比我高的，站我右边，比我矮的占我左边

const arr = [9, 6, 3, 15, 5, 7, 16, 4, 2, 13, 14];
let num = 0;
function quickSort(arr) {
  //递归执行，当数组人数只剩1或0人则排结束
  if (arr.length < 2) {
    return arr;
  }
  let flag = arr[0]; //从第一位开始快排
  let left = [];
  let right = [];
  //从第二位开始与我比个头
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > flag) {
      right.push(arr[i]);
    } else {
      left.push(arr[i]);
    }
  }
  num++;
  console.log(`第${num}次：`, left.concat(`MY-${flag}`, right));
  //第1次排完，左边6个，右边4个 [6, 3, 5, 7, 4, 2, "MY-9", 15, 16, 13, 14]
  //先左边又花了3次，结束后。在右边花了2次，共6次就排好了
  return quickSort(left).concat(flag, quickSort(right));
}
//快排法，时间复杂度上简单，空间复杂度上消耗较多一些（left,right的占内存）
const res2 = quickSort(arr);
console.log(res2);

---

原地快排法

根据二分逻辑，在快排算法基础上继续优化。
原地快排法：没用到 left,right，在原有数组上交换位置（原地就解决）

找一个目标值从它左边找到比它大的，再从右边找到比它小的，2数字交换位置。
双指针，左右各一个指针跑向中间跑，最后相遇则结束
目标值移动到左边比它大的那个前一位，此时左边肯定是都比它小的

const arr = [9, 6, 3, 15, 5, 7, 16, 4, 2, 13, 14];
  目标值移动 [↑, 6, 3, 2, ↓9,...];

function quick1(arr, start, end) {
  let init = start; //目标位置
  let flag = arr[init]; //目标值
  start++;
  while (start <= end) {
    while (arr[start] < flag) {
      start++;
    }
    while (arr[end] > flag) {
      end--;
    }
    //左边找到1个大值，右边找到了1个小值
    //start为目标位置，end为(arr长度 - 右指针向中间移动了几位)
    //start==end 则相遇了就结束
    //console.log(start, arr.length - end); //第一次是左3、右3
    if (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]]; //交换位置
      start++; //指针继续向中间跑
      end--;
    }
  }
  [arr[init], arr[start - 1]] = [arr[start - 1], arr[init]];
  return start;
}

let numx = 1;
function quickSort1(arr, start, end) {
  if (start < end) {
    let index = quick1(arr, start, end); //目标值所在位置
    console.log(`第${numx}次:`, arr);
    numx++;
    quickSort1(arr, start, index - 1); //双指针-左
    quickSort1(arr, index, end); //双指针-右
  }
  return arr;
}
const res3 = quickSort1(arr, 0, arr.length - 1);
console.log(res3);