排序

冒泡排序

遍歷數(shù)組，每次遍歷將最大（or最?。┑臄?shù)推到最前面

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解構(gòu)賦值
      }
    }
  } 
  return arr;
}

選擇排序

在無序區(qū)中選擇最小的數(shù)，將其與無序區(qū)第一個(gè)數(shù)交換位置

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

計(jì)數(shù)排序

用于確定范圍的整數(shù)的線性時(shí)間排序算法

function countingSort(arr) {
  let len = arr.length,
       resArr = [],
       countArr = [],
       min = Math.min.apply(undefined, arr),
       max = Math.max.apply(undefined, arr);
  // 統(tǒng)計(jì)每個(gè)值出現(xiàn)的次數(shù)
  for(let i = 0; i < len; i++) {
    countArr[arr[i]] = countArr[arr[i]] ? countArr[arr[i]] + 1 : 1;
  }
  // 從最小值->最大值，將計(jì)數(shù)逐項(xiàng)相加 ?
  for(let j = min; j < max; j++) {
    countArr[j+1] = (countArr[j+1] || 0) + (countArr[j] || 0);
  }
  // countArr中，下標(biāo)為arr數(shù)值，數(shù)據(jù)為arr數(shù)值出現(xiàn)的次數(shù)；反向填充數(shù)據(jù)進(jìn)resArr
  for(var k = len - 1; k >= 0; k--) {
    resArr[countArr[arr[k]] - 1] = arr[k];
    countArr[arr[k]]--;
  }
  return resArr;
}

快速排序

從數(shù)據(jù)集中，選擇一個(gè)基準(zhǔn)，一般以中間項(xiàng)為基準(zhǔn)，遍歷分為兩組后遞歸排序

function quickSort(arr) {
  let len = arr.length;
  // 定義左右數(shù)組
  let left = [], right = [];
  if(len <= 1) return arr;
  // 找基準(zhǔn)，并將基準(zhǔn)從原數(shù)組中刪除
  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));
}