JS实现排序算法

排序

冒泡排序

遍历数组，每次遍历将最大（or最小）的数推到最前面

function bubbleSort(arr) {
  let len = arr.length;
  for(let i = 0; i < len; i++) {
    for(let j = len - 1; j > i; j--) {
      if (arr[j] > arr[j-1]) {
        [arr[j], arr[j-1]] = [arr[j-1], arr[j]]; // ES6解构赋值
      }
    }
  } 
  return arr;
}

选择排序

在无序区中选择最小的数，将其与无序区第一个数交换位置

function selectionSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    // 寻找剩下的最小的数的索引
    let id = arr.indexOf(Math.min.apply(undefined, arr.slice(i)));
    if(i !== id) [arr[i], arr[id]] = [arr[id], arr[i]];
  }
  return arr;
}

计数排序

用于确定范围的整数的线性时间排序算法

function countingSort(arr) {
  let len = arr.length,
       resArr = [],
       countArr = [],
       min = Math.min.apply(undefined, arr),
       max = Math.max.apply(undefined, arr);
  // 统计每个值出现的次数
  for(let i = 0; i < len; i++) {
    countArr[arr[i]] = countArr[arr[i]] ? countArr[arr[i]] + 1 : 1;
  }
  // 从最小值->最大值，将计数逐项相加 ?
  for(let j = min; j < max; j++) {
    countArr[j+1] = (countArr[j+1] || 0) + (countArr[j] || 0);
  }
  // countArr中，下标为arr数值，数据为arr数值出现的次数；反向填充数据进resArr
  for(var k = len - 1; k >= 0; k--) {
    resArr[countArr[arr[k]] - 1] = arr[k];
    countArr[arr[k]]--;
  }
  return resArr;
}

快速排序

从数据集中，选择一个基准，一般以中间项为基准，遍历分为两组后递归排序

function quickSort(arr) {
  let len = arr.length;
  // 定义左右数组
  let left = [], right = [];
  if(len <= 1) return arr;
  // 找基准，并将基准从原数组中删除
  let pivotIndex = Math.floor(len / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  for(var i = 0; i < len - 1; i++) {
    if(arr[i] <= pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

插入排序

function insertSort(arr) {
  let len = arr.length;
  for(let i = 0; i < len; i++) {
    let tmp = arr[i];
    let j = i - 1;
    while(j >= 0 && arr[j] > tmp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = tmp;
  }
  return arr;
}

归并排序

function merge(left, right) {
  let tmp = [];
  while(left.length && right.length) {
    if(left[0] < right[0]) {
      tmp.push(left.shift());
    } else {
      tmp.push(right.shift());
    }
  }
  
  return tmp.concat(left, right);
}

function mergeSort(arr) {
  if(arr.length === 1) return arr;
  let mid = Math.floor(arr.length - 1),
      left = arr.slice(0, mid),
      right = arr.slice(mid);
   return merge(mergeSort(left), mergeSort(right));
}