排序

冒泡排序

/**
 * 冒泡排序
 */

function bubbleSort(arr, flag) {
  if (arr.length < 2) return arr;
  let length = arr.length;
  for (let i = 0; i < length; i++) {
    // 提前退出循环的标志位
    let flag = false;
    // console.log("i", i);
    for (let j = i + 1; j < length; j++) {
      // console.log("i-j", i, j);
      if (arr[i] > arr[j]) {
        let tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        flag = true; //表示有数据交换
      }
    }
    if (!flag) break; // 没有数据交换，提前退出
  }
  return arr;
}

// let arr1 = [2, 5, 3, 6, 1];
// console.log(`排序前：${arr1}\n排序后：${bubbleSort(arr1)}`);

let arr1 = Array.from(
  { length: 100000 },
  item => (item = Math.floor(Math.random() * Math.floor(100) + 1))
);
console.time("time");
bubbleSort(arr1);
console.timeEnd("time");

插入排序

/**
 * 插入排序
 */

function insertionSort(arr) {
  if (arr.length < 2) return arr;
  let length = arr.length;
  for (let i = 1; i < length; i++) {
    let value = arr[i]; // 第一个数据，为有序
    let j = i - 1;
    for (; j >= 0; j--) {
      // 与有序数据比较，若插入数小于前面的数据，交换位置
      if (arr[j] > value) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = value;
  }
  return arr;
}

let arr1 = [2, 5, 3, 6, 1];
console.log(`排序前：${arr1}\n排序后：${insertionSort(arr1)}`);

let arr2 = Array.from(
  { length: 100000 },
  item => (item = Math.floor(Math.random() * Math.floor(100) + 1))
);
console.time("timer");
insertionSort(arr2);
console.timeEnd("timer");

选择排序

/**
 * 选择排序
 */
function selectSort(arr) {
  if (arr.length < 2) return arr;
  for (let i = 0, len = arr.length; i < len; i++) {
    let k = i; //用于存放当前循环中最小值得index 默认为循环初识值的index
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[k]) {
        k = j;
      }
    }
    if (k !== i) {
      //将最小值与当前循环的第一个值互换位置
      let tmp = arr[k];
      arr[k] = arr[i];
      arr[i] = tmp;
    }
  }
  return arr;
}

let arr1 = Array.from(
  { length: 100000 },
  item => (item = Math.floor(Math.random() * Math.floor(100) + 1))
);
console.time("timer");
// console.log(`排序前：${arr1}\n排序后：${selectSort(arr1)}`);
selectSort(arr1);
console.timeEnd("timer");

快速排序

/*
 * @Author: HotSuitor
 * @Date: 2020-03-20 15:26:28
 * @LastEditors: hs
 * @LastEditTime: 2020-04-09 16:16:01
 * @Description: hotsuitor@qq.com
 */
function quickSort(arr, low, high) {
  if (low < high) {
    let m = partition(arr, low, high); // O(n)
    // let m = partition2(arr, low, high); // O(n)
    // arr[low..hight] -> arr[low..m-1], pivot, [m+1, high]
    quickSort(arr, low, m - 1);
    quickSort(arr, m + 1, high);
  }
  return arr;
}

function partition(arr, i, j) {
  let p = arr[i]; // 枢纽
  let m = i;
  for (let k = i + 1; k <= j; k++) {
    if (arr[k] < p) {
      m++;
      swap(arr, k, m);
    }
  }
  swap(arr, i, m);
  return m;
}

function swap(arr, i, j) {
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

function partition2(arr, left, right) {
  let pivot = arr[left];
  while (left < right) {
    while (left < right && arr[right] >= pivot) right = right - 1;
    arr[left] = arr[right];
    while (left < right && arr[left] < pivot) left = left + 1;
    arr[right] = arr[left];
  }
  arr[left] = pivot;
  return left;
}
let arr1 = [3, 2, 6, 5, 1, 9, 4];
// console.log(
//   `排序前数据：${arr1}\n排序后收据：${quickSort(arr1, 0, arr1.length - 1)}`
// );

let arr2 = Array.from({ length: 1000 }, item =>
  Math.floor(Math.random() * Math.floor(100) + 1)
);
console.time("timer");
console.log(quickSort(arr2, 0, arr2.length - 1));
console.timeEnd("timer");

注意

快速排序（递归实现）不适用数据超过60w(个人粗略测试)的数据排序，因为递归分隔区间排序过多容易导致爆栈 可以改用为迭代方式实现