[路飞]_你真的会排序吗？

function bubbleSort(arr){
  const len = arr.length;
  for(let i = 0;i<len-1;i++){
    for(let j = 0;j<len-1-i;j++){
      if(arr[j+1]<arr[j]) [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
    }
  }
  return arr;
}
复制代码

function selectSort(arr){
  for(let i = 0;i<arr.length-1;i++){
    let ind = i
    for(let j = i+1;j<arr.length;j++){
      if(arr[j]<arr[ind]) ind = j;
    }
    if(ind!==i){
      const tmp = arr[ind]
      arr[ind] = arr[i]
      arr[i] = tmp
    }
  }
  return arr;
}
复制代码

function insertSort(arr){
  for(let i = 1;i<arr.length;i++){
    for(let j = i;0<j;j--){
      if(arr[j]<arr[j-1]) [arr[j-1],arr[j]] = [arr[j],arr[j-1]]
    }
  }
  return arr;
}
复制代码

function shellSort(arr){
  const len = arr.length;
  let step = len >> 1;
  // 处理步长
  for(step;0<step;step = step >> 1){
    // 分组插入排序
    for(let i = step;i<len;i++){
      for(let j = i;j>=step&&arr[j]<arr[j-step];j-=step){
        [arr[j-step],arr[j]] = [arr[j],arr[j-step]]
      }
    }
  }
  return arr
}
复制代码

function mergeSort(arr){
  if(arr.length===1) return arr;
  function merge(left,right){
    const res = [];
    while(left.length&&right.length){
      if(left[0]<right[0])
        res.push(left.shift())
      else
        res.push(right.shift())
    }
    return [...res,...left,...right]
  }
  const mid = arr.length >> 1;
  return merge(
    mergeSort(arr.slice(0,mid)),
    mergeSort(arr.slice(mid))
  )
}
复制代码

function quickSort(arr){
  if(arr.length<2) return arr;
  const base = arr.pop(),left = [],right = [];
  for(let i = 0;i<arr.length;i++){
    if(arr[i]<base)
      left.push(arr[i])
    else
      right.push(arr[i])
  }
  return [...quickSort(left),base,...quickSort(right)]
}
复制代码

function handle(arr, left, right) {
  if(left>=right) return left;
  const base = arr[left]
  let l = left + 1;
  let r = right;
  while (l <= r) {
    if(arr[l] < base) {
      l++;
    } else if(arr[r] >= base) {
      r--;
    } else {
      // 存在 l<r && arr[l]>arr[r] 的情况 进行交换
      [arr[l],arr[r]] = [arr[r],arr[l]]
      l++,r--
    }
  }
  // 将起始元素与最后一个小于它的值交换
  [arr[left],arr[l-1]] = [arr[l-1],arr[left]]
  // 返回基准值下标
  return l - 1;
}
function quickSort(arr, l, r) {
  if (l < r) {
    const ind = handle(arr, l, r);
    // 递归处理基准值左侧区间
    quickSort(arr, l, ind - 1);
    // 递归处理基准值右侧区间
    quickSort(arr, ind + 1, r);
  }
  return arr;
}
复制代码

function countSort(arr){
  countArr = [],
  res = [];
  for(let i = 0;i<arr.length;i++){
    if(countArr[arr[i]] === undefined) countArr[arr[i]] = 0
    countArr[arr[i]]++
  }
  for(let i = 0;i<countArr.length;i++){
    while(countArr[i]){
      res.push(i)
      countArr[i]--
    }
  }
  return res;
}
复制代码

function countSort(arr){
  const min = Math.min(...arr),
  countArr = [],
  res = [];
  for(let i = 0;i<arr.length;i++){
    if(countArr[arr[i]-min] === undefined) countArr[arr[i]-min] = 0
    countArr[arr[i]-min]++
  }
  for(let i = 0;i<countArr.length;i++){
    while(countArr[i]){
      res.push(i+min)
      countArr[i]--
    }
  }
  return res;
}
复制代码

// 求低16位
function low16(num) {
  return num & 0xffff
}
// 求高16位
function __high16(num) {
  return (num & 0xffff0000) >> 16
}
function high16(num) {
  const h = __high16(num)
  return h > 32767 ? h - 32768 : h + 32768
}
function radixSort(arr) {
  // 获取输入数组长度
  const len = arr.length,
    // 创建计数数组
    count = Array(65536).fill(0),
    // 创建 temp 数组存储低 16 位排序后结果
    temp = Array(len)
  // 获取低十六位出现次数
  for (let i = 0; i < len; i++) {
    count[low16(arr[i])]++
  }
  // 计算前缀和
  for (let i = 1; i < 65536; i++) {
    count[i] += count[i - 1]
  }
  // 归位
  for (let i = len - 1; i >= 0; i--) {
    temp[--count[low16(arr[i])]] = arr[i]
  }
  // console.log(temp)
  // return temp
  // 清空 count
  for (let i = 0; i < 65536; i++) count[i] = 0
  // 获取高十六位出现次数
  for (let i = 0; i < len; i++) {
    count[high16(arr[i])]++
  }
  // 计算前缀和
  for (let i = 1; i < 65536; i++) {
    count[i] += count[i - 1]
  }
  // 归位
  for (let i = len - 1; i >= 0; i--) {
    arr[--count[high16(temp[i])]] = temp[i]
  }
  return arr
}
复制代码