排序算法

冒泡排序 O(n²)

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

function bubbleSort(arr) {
  let j = arr.length - 1
  while (j > 0) {
    let pot = 0
    for (let i = 0; i < j; i++) {
      if (arr[i] > arr[i + 1]) {
        pot = i /* 优化 */
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]
      }
      j = pot
    }
  }
  return arr
}

bubbleSort([4, 5, 6, 3, 2, 1, 8, 9, 7])

选择排序 O(n²)

function selectSort(arr) {
  let len = arr.length
  let minIndex
  for (let i = 0; i < len - 1; i++) {
    minIndex = i
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  return arr
}
selectSort([4, 5, 6, 3, 2, 1, 8, 9, 7])

插入排序 O(n²)

图书馆整理图书

function insertSort(arr) {
  let len = arr.length
  let preIndex, current
  for (let i = 1; i < len; i++) {
    preIndex = i - 1
    current = arr[i]
    while(preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}
insertSort([4, 5, 6, 3, 2, 1, 8, 9, 7])

希尔排序 O(nlogn)

归并排序 O(nlogn)

function merge(left, right) {
  let result = []

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }

  while (left.length)
    result.push(left.shift())

  while (right.length)
    result.push(right.shift())

  return result
}
// function mergeSortEx(arr, start, end) {
//   if (start < end) {
//     /* 分而 */
//     let middle = Math.floor((start + end) / 2),
//         left = mergeSortEx(arr, start, middle),
//         right = mergeSortEx(arr, middle + 1, end)
//     /* 治之 */
//     return merge(left, right)
//   }
//   return [arr[end]]
// }
// function mergeSort(arr) {
//   return mergeSortEx(arr, 0, arr.length - 1)
// }
function mergeSort(arr) {
  let len = arr.length
  if (len < 2) return arr
  let middle = Math.floor(len / 2),
      left = arr.slice(0, middle),
      right = arr.slice(middle)
  /* 分而治之 */
  return merge(mergeSort(left), mergeSort(right))
}
mergeSort([4, 5, 6, 3, 2, 1, 8, 9, 7])

快速排序 O(nlogn) 👍

function quickSort(arr) {
  let len = arr.length
  if (len < 2) {
    return arr
  } else {
    let flag = arr[0]
    let left = []
    let right = []
    for (let i = 1, temp; i < len; i++) {
      temp = arr[i]
      if (temp < flag) {
        left.push(temp)
      } else {
        right.push(temp)
      }
    }
    return quickSort(left).concat(flag, quickSort(right))
  }
}
quickSort([4, 5, 6, 3, 2, 1, 8, 9, 7])

原地快排

function partition(arr, start, end) {
  let pivotpos = start
  const pivot = arr[start] // 基准值

  for (let i = start + 1; i <= end; i++) {
    if (arr[i] < pivot) {
      pivotpos++
      if (pivotpos !== i) {
        [arr[pivotpos], arr[i]] = [arr[i], arr[pivotpos]]
      }
    }
  }
  arr[start] = arr[pivotpos]
  arr[pivotpos] = pivot

  return pivotpos
}
function quickSortEx(arr, start, end) {
  if (start < end) {
    let pivotpos = partition(arr, start, end)
    /* 分治 */
    quickSortEx(arr, start, pivotpos - 1)
    quickSortEx(arr, pivotpos + 1, end)
  }
}
function quickSort(arr) {
  quickSortEx(arr, 0, arr.length - 1)
  return arr
}
quickSort([4, 5, 6, 3, 2, 1, 8, 9, 7])

双指针

const quickSort = (function (arr, start, end) {
  /* 分治函数 */
  function partition(arr, start, end) {
    let v = arr[start]
    let i = start + 1
    let j = end

    while (i < j) {
      while (arr[i] <= v && i <= j) {
        i++
      }
      while (arr[j] >= v && j >= i) {
        j--
      }
      if (i < j) {
        [arr[j], arr[i]] = [arr[i], arr[j]]
      }
    }

    if (v > arr[j]) {
      [arr[start], arr[j]] = [arr[j], v]
    }

    return j
  }
  function quick(arr, start, end) {
    if (start < end) {
      let index = partition(arr, start, end)
      quick(arr, start, index - 1)
      quick(arr, index + 1, end)
    }
  }
  return function quickSort(arr) {
    quick(arr, 0, arr.length - 1)
    return arr
  }
})()
quickSort([4, 5, 6, 3, 2, 1, 8, 9, 7])

快排 + 插入排序

const quickSort = (function(arr) {
  function sort(arr, start, end) {
    if (start < end) {
      if (end - start <= 25) {
        insertSort(arr)
      } else {
        let pivotpos = partition(arr, start, end)
        sort(arr, start, pivotpos - 1)
        sort(arr, pivotpos + 1, end)
      }
    }
  }
  return function quickSort(arr) {
    sort(arr, 0, arr.length - 1)
    return arr
  }
})()
quickSort([4, 5, 6, 3, 2, 1, 8, 9, 7])