js 排序方法

冒泡排序

相邻两个对比，小的在前，

function bubbleSort(arr) {
  for (var outer = arr.length - 1; outer > 0; outer--) {
    var isSort = true;
    for (var inner = 0; inner < outer; inner++) {
      if (arr[inner] > arr[inner + 1]) {
        var temp = arr[inner];
        arr[inner] = arr[inner + 1];
        arr[inner + 1] = temp;
        isSort = false
      }
    }
    if (isSort) {
      break;
    }
  }
}

选择排序

从第一个开始找到最小的放最前面，依次

function selectionSort(arr) {
  var min = 0;
  for (var outer = 0; outer < arr.length - 1; outer++) {
    min = outer;
    for (var inner = outer + 1; inner < arr.length; inner++) {
      if (arr[min] > arr[inner]) {
        min = inner
      }
    }
    var temp = arr[outer];
    arr[outer] = arr[min];
    arr[min] = temp;
  }
}

插入排序

从第二个开始，和前面的对比，比前面小就换位置，不小就不动，依次

function insertSort(arr) {
  for (var outer = 1; outer < arr.length; outer++) {
    var temp = arr[outer];
    var inner = outer - 1
    while (inner >= 0 && temp < arr[inner]) {
      arr[inner + 1] = arr[inner];
      --inner;
    }
    arr[inner + 1] = temp
  }
}

硬编码间隔希尔排序

function shellSort(arr) {
  let gaps = [5, 3, 1]; //希尔排序间隔
  for (var g = 0; g < gaps.length; g++) {
    for (var i = gaps[g]; i < arr.length; i++) {
      var temp = arr[i];
      for (var j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {
        arr[j] = arr[j - gaps[g]]
      }
      arr[j] = temp
    }
  }
}

动态间隔序列希尔排序

function shellsort(arr) {
  var h = 1;
  while (h < arr.length / 3) {
    h = h * 3 + 1
  }
  while (h >= 1) {
    for (var i = h; i < arr.length; i++) {
      var temp = arr[i];
      for (var j = i; j >= h && arr[j - h] > temp; j -= h) {
        arr[j] = arr[j - h]
      }
      arr[j] = temp
    }
    h = (h - 1) / 3
  }
}

快速排序

通过第一个值将数组分为两个数组，大于该值的放在后面，小于该值的放在前面（利用递归）

function qSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var left = [];
  var right = [];
  var pivot = arr[0];
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] > pivot) {
      right.push(arr[i])
    } else {
      left.push(arr[i])
    }
  }
  return qSort(left).concat(pivot, qSort(right))
}

归并排序

function merge(left, right) {
  var result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] > right[0]) {
      result.push(right.shift())
    } else {
      result.push(left.shift())
    }
  }
  return result.concat(left, right)
}

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var middle = Math.floor(arr.length / 2);
  var left = arr.slice(0, middle);
  var right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

个人博客