JavaScript 实现常见排序算法

[fantasticit]

冒泡排序

冒泡排序重复遍历数组，依次比较 2 个元素，如这 2 个元素顺序错误，就交换位置。

• 比较相邻的元素，若前者大于后者就交换
• 对每一对相邻的元素执行上一部动作
• 经过前 2 步，最大的元素已经到数组最后一项，对剩下的前 n - 1 项重复前 2 步即可

function bubbleSort(arr) {
  let len = arr.length;

  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

选择排序

选择排序时间复杂度 O(n²)。

• 在未排序数列中，找到最小元素，存放到起始位置
• 从剩余未排序数列中，找到最小元素，放到已排序数列末尾
• 重复第 2 步知道完成

function selectSort(arr) {
  let len = arr.length
  let minIndex = 0
  
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  
  return arr
}

插入排序

插入排序首先构建有序数列，然后在有序数列中从后向前插入未排序元素。

• 将第 1 个元素看作已排序数列，将其后元素看作未排序数列
• 遍历未排序数列，将元素插入到已排序数列中的合适位置

function insertSort(arr) {
  let len = arr.length
  
  for (let i = 1; i < len; i++) {
    let j = i - 1;
    let tmp = arr[i]
    
    while (j >= 0 && arr[j] > tmp) {
      arr[j + 1] = arr[j]
      j--
    }
    
    arr[j + 1] = tmp
  }
  
  return arr
}

希尔排序

希尔排序是插入排序的更高效改进版。建立于插入排序的 2 点特性：

• 插入排序对几乎已经排列好的数列排序效率高
• 插入排序低效是因为 1 次只能移动 1 位

希尔排序的步骤。

• 选择一个增量序列，t1, t2, ..., tk，其中 ti > tj, tk = 1
• 按增量序列个数 k，对序列进行 k 趟排序
• 当增量因子为 1 时，整个序列进行 1 次排序

function shellSort(arr) {
  let len = arr.length;
  let gap = 1;

  while (gap < len / 3) {
    gap = gap * 3 + 1;
  }

  for (; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      let tmp = arr[i];
      let j = i - gap;

      while (j >= 0 && arr[j] > tmp) {
        arr[j + gap] = arr[j];
        j -= gap;
      }

      arr[j + gap] = tmp;
    }
  }

  return arr;
}

归并排序

归并排序是采用分治法的典型例子。

• 拆分数组为 2 部分
• 比较 2 部分数列
• 重复前 2 步

function mergeSort(arr) {
  let len = arr.length
  
  if (len <= 1) {
    return arr
  }
  
  let middle = len >> 1
  let left = arr.slice(0, middle)
  let right = arr.slice(middle)
  
  const merge = (left, right) => {
    let ret = []
    
    while (left.length && right.length) {
      if (left[0] < right[0]) {
        ret.push(left.shift())
      } else {
        ret.push(right.shift())
      }
    }
    
    while (left.length) {
      ret.push(left.shift())
    }
    
    while (right.length) {
      ret.push(right.shift())
    }
    
    return ret
  }
  
  return merge(mergeSort(left), mergeSort(right))
}

快速排序

快速排序采用分治法将 1 个数列分成 2 个子数列进行处理。

• 从数列中挑出一个基准值
• 将把基准值小的值，放在前，大的放在后
• 递归地重新排列划分后的 2 个子数列

function quickSort(arr, left, right) {
  if (arr.length <= 1) {
    return arr;
  }

  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat([pivot], quickSort(right));
}

[since123]

学习了