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

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));