排序算法

选择排序(Selection Sort)

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

插入排序(Insertion Sort)

一旦找到合适的位置，提前终止循环

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

优化之前：每一次的比较都要进行交换操作，交换操作包含 3 次赋值

优化版的插入排序：每一次的比较只赋值一次。内层循环终止后最后赋值 1 次。

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentValue = arr[i];
    for (var j = i; j > 0 && arr[j - 1] > currentValue; j--) {
      arr[j] = arr[j - 1];
    }
    //循环终止时j的位置是合适的位置。
    arr[j] = currentValue;
  }
  return arr;
}

归并排序(Merge Sort)

自顶向下

function mergeSort(arr) {
  const length = arr.length;
  const result = _mergeSort(arr, 0, length - 1);
  return result;
}
function _mergeSort(arr, leftIndex, rightIndex) {
  if (leftIndex >= rightIndex) return;
  const mid = Math.floor((leftIndex + rightIndex) / 2);
  _mergeSort(arr, leftIndex, mid);
  _mergeSort(arr, mid + 1, rightIndex);
  if (arr[mid] > arr[mid + 1]) {
    return merge(arr, leftIndex, mid, rightIndex);
  } else {
    return arr;
  }
}
function merge(arr, leftIndex, mid, rightIndex) {
  const length = rightIndex - leftIndex + 1;
  const result = Array(length);
  for (let i = leftIndex; i <= rightIndex; i++) {
    result[i - leftIndex] = arr[i];
  }
  let i = leftIndex,
    j = mid + 1;
  for (let k = leftIndex; k <= rightIndex; k++) {
    if (i > mid) {
      arr[k] = result[j - leftIndex];
      j++;
    } else if (j > rightIndex) {
      arr[k] = result[i - leftIndex];
      i++;
    } else if (result[i - leftIndex] < result[j - leftIndex]) {
      arr[k] = result[i - leftIndex];
      i++;
    } else {
      arr[k] = result[j - leftIndex];
      j++;
    }
  }
  return arr;
}

自底向上

function mergeSortBU(arr) {
  const { length } = arr;
  for (let size = 1; size <= length; size = size * 2) {
    for (let i = 0; i < length; i += size * 2) {
      //对arr[i....i+size-1]和[i+size...i+2*size-1]进行归并
      merge(arr, i, i + size - 1, Math.min(i + size + size - 1, length - 1));
    }
  }
  return arr;
}

快速排序(Quick Sort)

普通快速排序数据量达到十万级别容易溢出

function quickSort(arr) {
  _quickSort(arr, 0, arr.length - 1);
  return arr;
}
function _quickSort(arr, l, r) {
  if (l >= r) return;
  const p = partition(arr, l, r);
  _quickSort(arr, l, p - 1);
  _quickSort(arr, p + 1, r);
}
function partition(arr, l, r) {
  const v = arr[l];
  let j = l;
  for (let i = l + 1; i <= r; i++) {
    if (arr[i] < v) {
      let temp = arr[j + 1];
      arr[j + 1] = arr[i];
      arr[i] = temp;
      j++;
    }
  }
  let temp = arr[l];
  arr[l] = arr[j];
  arr[j] = temp;
  return j;
}

如果数组的数据趋于排序，则上述的快速排序方法创建的树严重失衡，复杂度会变成 O(n^2)

改进后的快速排序采用双路排序的方式

//双路排序
function quickSort2(arr) {
  _quickSort2(arr, 0, arr.length - 1);
  return arr;
}
function _quickSort2(arr, l, r) {
  if (l >= r) return;
  const p = partition2(arr, l, r);
  _quickSort2(arr, l, p - 1);
  _quickSort2(arr, p, r);
}

function partition2(arr, l, r) {
  const vi = Math.floor((l + r) / 2);
  swap(l, vi);
  const v = arr[l];
  //arr[l+1,i)<=v; arr(j,r]>=v
  let i = l,
    j = r;
  while (i <= j) {
    while (arr[i] < v) {
      i++;
    }
    while (arr[j] > v) {
      j--;
    }
    if (i > j) break;
    swap(arr, i, j);
    i++;
    j--;
  }
  return i;
}
function swap(arr, index1, index2) {
  [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
}

三路快排

//三路排序
function quickSort3(arr) {
  _quickSort3(arr, 0, arr.length - 1);
  return arr;
}
function _quickSort3(arr, l, r) {
  if (l >= r) return;
  const obj = partition3Ways(arr, l, r);
  _quickSort3(arr, l, obj.lt);
  _quickSort3(arr, obj.gt, r);
}

function partition3Ways(arr, l, r) {
  const vi = Math.floor((l + r) / 2);
  swap(l, vi);
  const v = arr[l];
  //arr[l+1,lt]<v; arr[gt,r]>v;[lt+1,i)===v
  let lt = l,
    gt = r + 1,
    i = l + 1;
  while (i < gt) {
    if (arr[i] < v) {
      swap(arr, lt + 1, i);
      lt++;
      i++;
    } else if (arr[i] > v) {
      swap(arr, gt - 1, i);
      gt--;
    } else {
      i++;
    }
  }
  swap(arr, l, lt);
  lt--;
  return { lt: lt, gt: gt };
}
function swap(arr, index1, index2) {
  [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
}