排序算法

下面排序会用到的一些工具函数

function checkArray(arr) {
  return Array.isArray(arr);
}

function swap(arr, leftIndex, rightIndex) {
  const rightItem = arr[rightIndex];
  arr[rightIndex] = arr[leftIndex];
  arr[leftIndex] = rightItem;
}

冒泡排序

冒泡排序的原理如下，从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到 length - 2 的位置。

// 冒泡到 arr.length - 2 也就是倒数第二个就可以停止了
function bubble(arr) {
  if (!checkArray(arr)) return;

  console.time("calc-bubble");
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
    }
  }
  console.timeEnd("calc-bubble");
  return arr;
}

const list = [5, 7, 6, 2, 4, 3, 1];

const result = bubble(list);
console.log("result", result);

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

插入排序

插入排序的原理如下。第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

function insertion(array) {
  if (!checkArray(array)) return;
  for (let i = 1; i < array.length; i++) {
    for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
      swap(array, j, j + 1);
  }
  return array;
}

选择排序

选择排序的原理如下。遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

function selectionSort(array) {
  if (!checkArray) return;
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      minIndex = array[j] < array[minIndex] ? j : minIndex;
    }
    swap(array, i, minIndex);
  }
  return array;
}

TODO

• [] 快排
• [] 归并排序
• [] 三路快排
• [] 堆排序
• [] 系统自带排序实现