JavaScript排序算法总结

0. 打乱数组

源代码

Array.prototype.shuffle = function () {
  let m = this.length, i;
  while (m) {
    i = (Math.random() * m--) >>> 0;
    [this[m], this[i]] = [this[i], this[m]];
  }
  return this;
}

测试

let myArr = Array.from(Array(10), (_, k) => k)
console.log(myArr)
myArr.shuffle()
console.log(myArr)

测试结果

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
[ 7, 4, 0, 2, 3, 6, 9, 5, 8, 1 ]

1. 插入排序

源代码

let InsertSort = arr => {
  let len = arr.length, i, j;
  for (i = 1; i < len; ++i) {
    let temp = arr[i];
    for (j = i; j > 0 && arr[j - 1] > temp; --j) {
      arr[j] = arr[j - 1];
    }
    arr[j] = temp;
  }
}

测试

let arr =  Array.from(Array(10), (_, k) => k).shuffle()
console.log(arr)
InsertSort(arr)
console.log(arr)

测试结果

[ 9, 5, 3, 1, 7, 2, 4, 0, 6, 8 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

2. 冒泡排序

源代码

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

测试

let arr =  Array.from(Array(10), (_, k) => k).shuffle()
console.log(arr)
BubbleSort(arr)
console.log(arr)

测试结果

[ 8, 9, 6, 2, 1, 7, 0, 3, 5, 4 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

3. 选择排序

let SelectSort = arr => {
  let len = arr.length, j, t;
  for (let i = 0; i < len - 1; i++) {
    t = i
    for (j = i + 1; j < len; j++) {
      (arr[j] < arr[t]) && (t = j);
    }
    (t != i) && ([arr[i], arr[t]] = [arr[t], arr[i]]);
  }
}

测试

let arr = Array.from(Array(10), (_, k) => k).shuffle()
console.log(arr)
SelectSort(arr)
console.log(arr)

测试结果

[ 1, 0, 6, 8, 7, 4, 3, 9, 5, 2 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

4. 归并排序

let merge = (left, right) => {
  let res = [], indexLeft = 0, indexRight = 0;
  while (indexLeft < left.length && indexRight < right.length) {
    left[indexLeft] < right[indexRight] ? res.push(left[indexLeft++]) : res.push(right[indexRight++]);
  }
  res = indexLeft < left.length ? res.concat(left.slice(indexLeft)) : res.concat(right.slice(indexRight));
  return res;
}

let MergeSortRe = arr => {
  if (arr.length <= 1) {
    return arr;
  }
  let mid = parseInt(arr.length / 2);
  return merge(MergeSortRe(arr.slice(0, mid)), MergeSortRe(arr.slice(mid)));
}

let MergeSort = arr => {
  let res = MergeSortRe(arr);
  for (let i = 0; i < arr.length; i++) {
    arr[i] = res[i];
  }
  return arr;
}

测试

let arr = Array.from(Array(10), (_, k) => k).shuffle()
console.log(arr)
MergeSort(arr)
console.log(arr)

测试结果

[ 6, 9, 1, 7, 8, 5, 2, 3, 4, 0 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

5. 快速排序

源代码

let partition = (arr, begin, end) => {
  if (begin >= end) {
    return -1;
  }
  let i = begin + 1, j = end;
  while (i < j) {
    if (arr[i] > arr[begin]) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      j--;
    } else {
      i++;
    }
  }
  (arr[i] >= arr[begin]) && i--;
  [arr[i], arr[begin]] = [arr[begin], arr[i]];
  return i;
}

let QuickSort = (arr, begin = 0, end = arr.length - 1) => {
  let pos = partition(arr, begin, end);
  if (pos != -1) {
    QuickSort(arr, begin, pos - 1);
    QuickSort(arr, pos + 1, end);
  }
}

测试

let arr = Array.from(Array(10), (_, k) => k).shuffle()
console.log(arr)
QuickSort(arr)
console.log(arr)

测试结果

[ 8, 6, 1, 9, 7, 2, 5, 4, 3, 0 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

6. 堆排序

源代码

let maxHeap = (arr, start, end) => {
  let dad = start;
  let son = dad * 2 + 1;
  while (son <= end) {
    if (son + 1 <= end && arr[son] < arr[son + 1]) {
      son++;
    }
    if (arr[dad] > arr[son]) {
      return;
    } else {
      [arr[dad], arr[son]] = [arr[son], arr[dad]];
      dad = son;
      son = dad * 2 + 1;
    }
  }
}

let HeapSort = arr => {
  let len = arr.length;
  for (i = parseInt(len / 2) - 1; i >= 0; i--) {
    maxHeap(arr, i, len - 1);
  }
  for (i = len - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    maxHeap(arr, 0, i - 1);
  }
}

测试

let arr = Array.from(Array(10), (_, k) => k).shuffle()
console.log(arr)
HeapSort(arr)
console.log(arr)

测试结果

[ 2, 3, 5, 8, 9, 1, 4, 6, 0, 7 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]