前端算法之美-排序算法

即将上线前端算法之美-查找算法

即将上线前端算法之美-进阶篇

历经一个多月，我又回来了。最近做了三件事，刷了 leetcode easy 的题，看完了《剑指Offer》，《学习JavaScript数据结构和算法》。手写算法的能力也算有所增进，其实算法最重要的是理解，理解了各种经典算法，各类经典题型，面对变换的题目，除了边界条件可能需要小心处理，其他部分都会游刃有余。下面开始介绍最经典的几种排序算法。

我会先实现几个辅助函数，算法中经常会使用。

function swap(array, i , j) {
  const temp = array[i];
  array[i] = array[j];
  array[j] = temp;

  // 你当然也可以使用下面的方式进行元素交换，但是性能没有上面好。
  // [array[i], array[j]] = [array[j], array[i]];
}

function less(a, b) {
  return b > a;
}

function findMaxValue(array) {
  return Math.max(...array);
}

function findMinValue(array) {
  return Math.max(...array);
}

冒泡排序是简单最基础的算法，比较两个相邻的元素，谁大谁往后排。顾名思义，元素像气泡一样，不断往上（后）冒。

下面是冒泡排序的实现：

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

const ret = [5, 3, 1, 2, 4];
bubbleSort(ret);
console.log(ret);

我们可以优化一下冒泡排序的循环次数，j 的循环体内，我们每次两两交换，其实第一次就可以知道元素中的最大值，所以可以减少这部分的重复循环。下面是优化之后的版本：

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

const ret = [5, 3, 1, 2, 4];
bubbleSort(ret);
console.log(ret);

选择排序关键在于选择两个字，其他排序方式也在于“排序”前面的关键字，这貌似是废话。每次选择最小的元素，与首位交换。

下面是选择排序的实现：

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
  let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    swap(array, i, minIndex);
  }
}
const ret = [5, 3, 1, 2, 4];
selectionSort(ret);
console.log(ret);

插入排序遍历到每一步的时候都是有序的，遍历都每一步都对数据进行排序。比如，第一项比第二项大，第二项插入到第一项前面。

每次保存当前要插入的值，将大的值都往后移一位，判断循环的值比当前要插入值小，即插入后面一位。下面是插入排序的代码：

function insertionSort(array) {
  let temp = 0;
  for (let i = 1; i < array.length; i++) {
    let j = i;
    temp = array[i];
    while(j > 0 && less(temp, array[j - 1])) {
      array[j] = array[j - 1];
      j--;
    }
    array[j] = temp;
  }
}
const ret = [5, 3, 1, 2, 4];
insertionSort(ret);
console.log(ret);

归并排序比较经典，是一种分而治之的算法。我们经常会用到这种算法，JavaScript中的数组排序 sort，在FireFox里的实现用的就是归并排序，而Chrome里用的是快排。

归并排序就是将数组一分为二（当然也可以一分为三，看算法实现），递归划分，最后将划分到只剩一个或者二个元素，然后将元素排序，最后再重组被递归的数组。它由两部分组成，一是划分，二是排序重组。下面是归并排序算法

function mergeSort(array, lo, hi) {
  if (lo >= hi) return;

  const mid = Math.floor(lo + (hi - lo) / 2);
  mergeSort(array, lo, mid);
  mergeSort(array, mid + 1, hi);

  merge(array, lo, mid, hi);
}
function merge(array, lo, mid, hi) {
  let i = lo;
  let j = mid + 1;
  const aux = [];

  for (let k = lo; k <= hi; k++) {
    aux[k] = array[k];
  }

  for (let k = lo; k <= hi; k++) {
    if (i > mid) {
      array[k] = aux[j++];
    } else if (j > hi) {
      array[k] = aux[i++];
    } else if (less(aux[j], aux[i])) {
      array[k] = aux[j++];
    } else {
      array[k] = aux[i++];
    }
  }
}

const ret = [5, 3, 1, 2, 4];
mergeSort(ret, 0, ret.length - 1);
console.log(ret);

merge函数利用下标的方式，实现起来代码会长一点，《算法（第4版）》就是用下标处理，但是实现方式还有点差别。顺便提一句，merge函数非常关键，这是我们很多算法的基础，比如两个有序数组合并成一个有序数组，直接调用merge函数就能得到结果。

下面我实现一种不传递下标的方式，更易读，也是《学习JavaScript数据结构和算法》一书的方式。

function mergeSort(array) {
  if (array.length <= 1) return array;

  const mid = Math.floor(array.length / 2);
  const left = mergeSort(array.slice(0, mid));
  const right = mergeSort(array.slice(mid));
  return merge(left, right);
}
function merge(left, right) {
  let i = 0;
  let j = 0;
  let ret = [];

  while(i < left.length && j < right.length) {
    if (less(left[i], right[j])) {
      ret.push(left[i]);
      i++;
    } else {
      ret.push(right[j]);
      j++;
    }
  }
  return ret.concat(i < left.length ? left.slice(i) : right.slice(j));
}

let ret = [5, 3, 1, 2, 4];
ret = mergeSort(ret);
console.log(ret);

快排实在太经典了，它的特点就是快，应用在各个领域当中。

在实现快排之前，我们说一下阮一峰大佬的快排代码（消费一下，大佬应该不会在意吧），他在最后用了 concat 方法连接左右被划分的元素，而concat是会新生成一个数组，导致并没有利用快排原地排序（不借助额外的内存空间）的特性。快排快一部分原因是内循环代码少，更重要的是它不会开辟新的内存空间。

快排的原理，每次找到一个主元（pivot），将比主元小的放左边，比主元大的放左边。按照正常情况，在操作数组前还需要对数组进行随机排序，避免快排退化到 O(n^2) 的时间复杂度，这里就先省略吧。下面我们来实现一下快排：

function quickSort(array, lo, hi) {
  if (lo >= hi) return;

  const j = partition(array, lo, hi);
  quickSort(array, lo, j - 1);
  quickSort(array, j + 1, hi);
}

function partition(array, lo, hi) {
    const temp = array[lo];
    let i = lo;
    let j = hi + 1;

    while(true) {
      while (less(array[++i], temp)) {
          if (i === hi) break;
      }
      while (less(temp, array[--j])) {
          if (j === lo) break;
      }
      if (i >= j) break;
      exchange(array, i, j);
    }

    exchange(array, lo, j);
    return j;
}
let ret = [5, 3, 1, 2, 4];
quickSort(ret, 0, ret.length - 1);
console.log(ret);

计数排序是一种整数算法，它的时间复杂度非常快，O(n + k)，k为临时计数数组的大小，这个值取决于数组的最大值，所以这个算法非常优秀，但是它的使用场景非常有限，数组内容必须是整数，并且整数之间差值不能太多。

下面是计数排序的代码：

function countSort(array) {
  if (array.length < 2) {
    return array;
  }

  const maxValue = findMaxValue(array);

  const counts = new Array(maxValue + 1);
  array.forEach(item => {
    if (counts[item]) {
      counts[item] = 0;
    }
    count[item]++;
  });

  let sortedIndex = 0;
  counts.forEach((count, i) => {
    while(count > 0) {
      array[sortedIndex++] = i;
      count--;
    }
  });
  return array;
}

基数排序根据数字的有效位或者基数（个位，十位，百位），将整数直接放到每一个进位的桶里，每一桶排完序，数组也就有序了。它有两种方式，可以从个位开始排序，也可以从最高位开始排序（需要特殊处理没有最高位的数字）。这也是使用场景非常有限的算法，一般是位数比较相近的数字或者字母，比如电话号码，身份证等。

下面是基数排序的算法

function radixSort(array, radixBase = 10) {
  if (array.length < 2) {
    return array;
  }

  const minValue = findMinValue(array);
  const maxValue = findMaxValue(array);

  let carry = 1;
  while((maxValue - minValue) / carry >= 1) {
    array = countSortForRadix(array, radixBase, carry, minValue);
    carry *= radixBase;
  }
  return array;
}

function countSortForRadix(array, radixBase, carry, minValue) {
  let bucketIndex = 0;
  const buckets = [];
  const aux = [];
  for (let i = 0; i < radixBase; i++) {
    buckets[i] = 0;
  }

  for (let i = 0; i < array.length; i++) {
    bucketsIndex = Math.floor((array[i] - minValue) / carry) % radixBase;
    buckets[bucketIndex]++;
  }

  for (let i = 0; i < radixBase; i++) {
    buckets[i] += buckets[i - 1];
  }

  for (let i = array.length - 1; i >= 0; i--) {
    bucketsIndex = Math.floor((array[i] - minValue) / carry) % radixBase;
    aux[buckets[bucketIndex]] = array[i];
  }

  for (let i = 0; i < array.length; i++) {
    array[i] = aux[i];
  }
  return array;
}
const ret = [5, 3, 1, 2, 4];
radixSort(ret);
console.log(ret);

桶排序的原理，将元素划分到各个桶中，排完序再合并，和归并排序有些类似。这个算法的性能和元素密集程度有关，元素非常稀疏，则需要更多的桶。

function bucketSort(array, bucketSize = 5) {
  if (array.length < 2) {
    return array;
  }

  const buckets = createBuckets(array, bucketSize);
  return sort(buckets);
}

function createBuckets(array, bucketSize) {
  const minValue = findMinValue(array);
  const maxValue = findMaxValue(array);

  const bucketCount = ((maxValue - minValue) / bucketSize) + 1;

  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  }

  for (let i = 0; i < array.length; i++) {
    const bucketIndex = Math.floor((array[i] - minValue) / bucketSize);
    buckets[bucketIndex].push(array[i]);
  }

  return buckets;
}

function sort(buckets) {
  const sortedArray = [];
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i] !== null) {
      insertionSort(buckets[i]);
      sortedArray.push(...buckets[i])
    }
  }
  return sortedArray;
}
const ret = [5, 3, 1, 2, 4];
bucketSort(ret);
console.log(ret);

堆排序是基于优先队列，所以使用场景有限。每次取出最大值，然后进行变换操作，改变队列（一般是二叉堆）的顺序，再取出次大值，以此往复。

这里就先不实现堆排序了，它需要先构造一个二叉堆。

每次写快排和归并排序，总是无法一步到位，它们的边界条件处理需要很小心，也难怪这两个算法是现在最流行的算法之一。最近看到30多岁程序员开滴滴，我在想，我们将青春都奉献给了眼前的屏幕，有时候是否值得，这个答案等我30岁再去解锁吧，我们现在能做的就是全身心投入到学习中。

前端算法之美-排序算法

前端算法之美-排序算法

Recommend

可能是最简单的操作系统书籍

可能是最快的前端下拉刷新组件

互联网人如何学习英语

深入浅出计算机组成原理

VSCode多进程架构和插件加载原理

Get Audio Analysis for a Track

Soundlights with ESP8266 and NeoPixel Strip

Figures: Streaming Systems Book

Streaming Systems Book

Database Internals

About Joyk