「算法」排序算法

冒泡排序 O(n2)

比较所有相邻的两个项,如果第一个比第二个大,则交换他们.元素项向上移动至正确位置.

代码示例

const bubbleSort = (array) => {
  const {length} = array;
  for(let i = 0; i < length; i++) {
    for(let j = 0; j < length - 1 - i; j ++){
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}
bubbleSort([5, 3, 1, 6]); // [1, 3, 5, 6]

选择排序 O(n2)

选择排序算法是一种原址比较排序算法。

思路

找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值将其放在第二位,以此类推。

代码示例

function selectSort (array) {
  const {length} = array;
  let indexMin;
  for(let i = 0; i < length; i++) {
    indexMin = i;
    for(let j = i; j < length; j ++){
      if (array[indexMin] > array[j]) {
        indexMin = j;
      }
    }
    if (i !== indexMin) {
      [array[i], array[indexMin]] = [array[indexMin], array[i]];
    }
  }
  return array;
}
selectSort([5,3, 1, 6]); // [1, 3, 5, 6]

插入排序

插入排序每次排一个数组项,以此方式构建最后的排序树组。

思路

假定第一项已经排序了。接着,它和第二项进行比较————第二项是应该待在原位还是插到第一项之前呢?这样,头两项就已正确排序,接着和第三项比较(它时该插入到第一、第二还是第三的位置呢),以此类推。

代码示例

function insertSort (array) {
  const {length} = array;
  let temp;
  for(let i = 0; i < length; i++) {
    let j = i;
    temp = array[i];
    while(j > 0 && (array[j - 1] > temp)) { // j > 0 且 前一个项大于后一项
      array[j] = array[j - 1];
      j--;
    }
    array[j] = temp;
  }
  return array;
}
insertSort([3, 5, 1, 4, 2]); // [1, 2, 3, 4, 5]

归并排序 O(nlog(n))

归并排序是一个可以实际使用的排序算法。是一种分而治之算法。
Array.sort是有浏览器厂商自行实现的算法,例如:Mozilla Firefox使用归并排序算法作为Array.prototype.sort的实现,而Chrome(V8引擎)使用了快速排序的变体。

思路

将原始数组切分成较小的数组,直至每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。

代码示例

function mergeSort(array) {
  const { length } = array;
  if (length > 1) {
    let middle = Math.floor(length / 2);
    const left = mergeSort(array.slice(0, middle));
    const right = mergeSort(array.slice(middle, length));
    array = merge(left, right);
  }
  console.log(array)
  return array;
}

function merge(left, right) {
  let i = 0;
  let j = 0;
  const result = [];
  while(i < left.length && j<right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++])
  }
  return result.concat( i < left.length ? left.slice(i) : right.slice(j));
}

mergeSort([3, 5, 1, 4, 2]); // [1, 2, 3, 4, 5]

快速排序 O(nlog(n))

快速排序也许是最常用的排序算法了。且性能通常比其他复杂度为O(nlog(n))的排序算法要好。和归并排序一样,快速排序也是用分而治之的方法,将原始数组分为较小的数组。

思路

  1. 首先,从数组中选择一个值作为主元(pivot),也就是数组中间的值.
  2. 创建两个指针(引用),左边一个指向数组第一个值,右边一个指向数组最后一个值.移动左指针直到我们找到一个比主元的值,移动右指针直到找到一个比主元小的值,然后交换它们,重复这个过程,直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前,比主元大的值都排在主元之后。这一步叫做划分操作。
  3. 接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的子数组)重复之前的两个步骤,直至数组已完全排序。

代码示例

function quickSort(array) {
  return quick(array, 0, array.length - 1);
}

function quick(array, left, right) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right);
    if (left < index - 1) quick(array, left, index - 1);
    if (index < right) quick(array, index, right);
  }
  return array;
}

function partition(array, left, right) {
  let pivot = array[Math.floor((left + right) / 2)];
  let i = left;
  let j = right;
  while (i <= j) {
    while (pivot > array[i]) i++;
    while (array[j] > pivot) j--;
    if (i <= j) {
      [array[j], array[i]] = [array[i], array[j]];
      i++;
      j--;
    }
  }
  return i;
}

quickSort([3, 5, 1, 4, 2]); // [1, 2, 3, 4, 5]

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://demongao.com/2020/03/算法排序算法

Buy me a cup of coffee ☕.