手写排序

给定一个数组，让它从小到大排序。相信大家在面试的时候，面试官通常会问的一道题。

const arr = [9, 6, 4, 3, 5, 2, 8, 10, 20];

有一个网站还是比较好的，可视化算法https://visualgo.net/en/sorting
首先，先写一个数组交换方法，它需要的参数为一个数组，两个要交换的下标。

const swap = (arr, i, j) => {
  const temp = arr[i];  // 创建一个变量作为临时存储
  // 进行交换
  arr[i] = arr[j];
  arr[j] = arr[i]
}

从简单开始

在排序的时候，第一个想法就是简单粗暴。
前一个和后一个比，如果符合条件就交换。
开始手写：

const sort = (arr) => {
  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      swap(arr, i, j);
    }
  }
  return arr;
}

以下是完整实现

See the Pen changeSort by 韦宗圻 (@weizongqi1990) on CodePen.

以上就完成了一个简单的排序（可以打开console查看结果）。

冒泡排序

上面已经很简单的进行排序，但是效率还是非常低的。下面开始手写总所周知的冒泡排序：

const sort = (arr) => {
  for(let i = 0; i < arr.length; i++) {
    for(let j = arr.length - 1; j > i; j--) {
      if (arr[j - 1] > arr[j]) {
        swap(arr, j - 1, j);
      }
    }
  }
  return arr;
}

冒泡排序顾名思义，数组的最后一个元素会像冒泡一个往上冒泡。这里要注意的是对比和交换的时候是末尾和上一个元素对比不能写为

// 这个是错误的
if (arr[i] > arr[j]) {
  swap(arr, i, j);
}

但还有个问题，这样排序还是可以去提升它的性能的，我们可以去记录下是否已经排序了

const sortPerform = (arr) => {
  let flag = true;
  for(let i = 0; i < arr.length && flag; i++) {
    flag = false;
    for(let j = arr.length - 1; j > i; j--) {
      if (arr[j - 1] > arr[j]) {
        swap(arr, j - 1, j);
        flag = true;
      }
    }
  }
  return arr;
}

完整代码：

See the Pen BubbleSort by 韦宗圻 (@weizongqi1990) on CodePen.

归并排序

在Firefox里面，数组里的sort的排序使用的是归并排序，因为它的时间复杂度稳定，但有个缺点是它的空间复杂度比较高。
它的原理是采用递归的形式把数组不断的拆成最小数组，然后再合并起来。

const sort = (arr) => {
  return sortOrigin(arr);
}
const sortOrigin = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = Math.floor(arr.length / 2);
  const left = arr.slice(0, pivot);
  const right = arr.slice(pivot, arr.length);
  return merge(sortOrigin(left), sortOrigin(right));
}
const merge = (left, right) => {
  const result = [];
  while(left.length && right.length) {
    result.push(left[0] < right[0] ? left.shift() : right.shift());
  }
  return [
    ...result,
    ...left,
    ...right
  ];
}

以下是完整代码：

See the Pen MergeSort by 韦宗圻 (@weizongqi1990) on CodePen.

快速排序

快速排序是在chrome浏览器上使用的一种排序，它的平均算法复杂度与归并是一样的。但是空间复杂度要比归并排序要低。

const sort = (arr) => {
  sortOrigin(arr, 0, arr.length - 1);
  return arr;
}
const sortOrigin = (arr, i, j) => {
  if (i >= j) {
    return;
  }
  const pivot = partial(arr, i, j);
  sortOrigin(arr, i, pivot - 1);
  sortOrigin(arr, pivot + 1, j);
};
const partial = (arr, i, j) => {
  let pivot = arr[Math.floor((i + j) / 2)];
  while(i < j) {
    while (i < j && arr[j] >= pivot) {
      j--;
    }
    swap(arr, i, j);
    while (i < j && arr[i] <= pivot) {
      i++;
    }
    swap(arr, i, j);
  }
  return i;
}

完整例子

See the Pen QuickSort by 韦宗圻 (@weizongqi1990) on CodePen.