关于算法-数据结构:算法排序

function createArray(num) {  let res = [];  for (let i = 0; i < num; i++) {    res.push(Math.floor(Math.random() * num));  }  return res;}function checkArraySorted(arr) {  let res = true;  for (let i = 0, length = arr.length - 1; i < length; i++) {    if (arr[i] > arr[i + 1]) {      res = false;      break;    }  }  return res;}let arr = createArray(10000);/** * 冒泡排序 * 复杂度: O(n2) * 327.085ms */function bubbleSort(arr) {  let length = arr.length;  for (let i = 0; i < length; i++) {    for (let j = 0; j < length - i - 1; j++) {      if (arr[j] > arr[j + 1]) {        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];      }    }  }}/** * 抉择排序 * 复杂度: O(n2) * 94.6 ms */function selectSort() {  let length = arr.length;  for (let i = 0; i < length; i++) {    let minIndex = i;    for (let j = i + 1; j < length; j++) {      if (arr[j] < arr[minIndex]) {        minIndex = j;      }    }    if (minIndex > i) {      [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];    }  }}/** * 插入排序 * 工夫复杂度: 最差为O(n2), 空间复杂度: O(1) * 5.284ms * 思维: 假如前 i - 1 个元素曾经排序好了, 为第 i 个元素在前 i 个元素中找到正确的地位 * 适宜: nearly sorted数组 * 个性: 稳固; 对于 nearly sorted 数组, 工夫复杂度降为 O(1) */function insertSort(arr) {  let length = arr.length;  for (let outer = 1; outer < length; outer++) {    let inner = outer;    while (inner > 0 && arr[outer] < arr[inner - 1]) {      arr[inner] = arr[inner - 1];      inner--;    }    arr[inner] = arr[outer];  }}/** * 归并排序 * 工夫复杂度: O(nlogn) 空间复杂度: O(nlogn) * 27.349ms  */function mergeSort(arr) {  if (arr.length > 1) {    let mid = arr.length >> 1;    let left = mergeSort(arr.slice(0, mid));    let right = mergeSort(arr.slice(mid));    arr = merge(left, right);  }  return arr;  function merge(left, right) {    let i = j = 0;    let res = [];    while (left[i] && right[j]) {      if (left[i] < right[j]) {        res.push(left[i]);        i++;      } else {        res.push(right[j]);        j++;      }    }    return res.concat(left[i] ? left.slice(i) : right.slice(j));  }}/** * 疾速排序 * 工夫复杂度: O(nlogn) * 22.066ms *  */function quickSort(arr) {  if (arr.length < 2) {    return arr;  }  let base = arr[0];  let less = [];  let greater = [];  for (let i = 1, length = arr.length; i < length; i++) {    if (arr[i] > base) {      greater.push(arr[i]);    } else {      less.push(arr[i]);    }  }  return quickSort(less).concat(base).concat(quickSort(greater));}function quickSort2(arr) {  return quick(arr, 0, arr.length - 1);  function quick(arr, left, right) {    if (right > left) {      let index = partition(arr, left, right);      if (left < index - 1) {        quick(arr, left, index - 1);      }      quick(arr, index, right);    }    return arr;  }  function partition(arr, left, right) {    let pivot = arr[(left + right) >> 1];    while (left <= right) {      while (arr[left] < pivot) {        left++;      }      while (arr[right] > pivot) {        right--;      }      if (left <= right) {        [arr[left], arr[right]] = [arr[right], arr[left]];        left++;        right--;      }    }    return left;  }}console.time();arr = quickSort2(arr);console.timeEnd();console.log(checkArraySorted(arr));