常用排序算法的JavaScript实现

之前做过常用排序算法的python实现，因为python的语法简单，个人喜欢用python去练习算法题目，毕竟自己是以JavaScript作为主力开发语言的，python仅仅知道基础语法，所以以后准备用JavaScript去练习算法。先把常用排序算法用JavaScript重新实现一遍吧。

直接给答案，就不介绍了，思路可以看python篇。

冒泡排序

/**
 * @desc 冒泡排序
 * @param {number[]} list
 */
function bubbleSort(list){
  for(let i=list.length-1; i>0; i--){
    for(let j=0; j<i; j++){
      if(list[j] > list[j+1]){
        let cur = list[j]
        list[j] = list[j+1]
        list[j+1] = cur
      }
    }
  }
}

let arr = [3, 14, 6, 4, 8, 7, 25, 9, 0, 12, 13, 24,10, 17]
bubbleSort(arr)
// arr: [0,  3,  4,  6,  7,  8, 9, 10, 12, 13, 14, 17, 24, 25]
console.log("arr:", arr)

选择排序

/**
 * @desc 选择排序
 * @param {number[]} list
 */
function selectionSort(list){
  for(let i=list.length; i>0; i--){
    let posMax = 0
    for(let j=0; j<i; j++){
      if(list[j] > list[posMax]){
        posMax = j
      }
    }
    let cur = list[posMax]
    list[posMax] = list[i-1]
    list[i-1] = cur
  }
}
let arr = [3, 14, 6, 4, 8, 7, 25, 9, 0, 12, 13, 24,10, 17]
selectionSort(arr)
// arr: [0,  3,  4,  6,  7,  8, 9, 10, 12, 13, 14, 17, 24, 25]
console.log("arr:", arr)

插入排序

/**
 * @desc 插入排序
 * @param {number[]} list
 */
function insertionSort(list){
  for(let i=1; i<list.length; i++){
    let cur = list[i]
    let pos = i
    while (pos > 0 && list[pos-1] > cur) {
      list[pos] = list[pos-1]
      pos -= 1
    }
    list[pos] = cur
  }
}

let arr = [3, 14, 6, 4, 8, 7, 25, 9, 0, 12, 13, 24,10, 17]
insertionSort(arr)
// arr: [0,  3,  4,  6,  7,  8, 9, 10, 12, 13, 14, 17, 24, 25]
console.log("arr:", arr)

希尔排序

/**
 * @desc 希尔排序
 * @param {number[]} list
 */
function shellSort(list){
  let gap = Math.floor(list.length / 2)
  while(gap >= 1){
    insertSortByGap(list, gap)
    gap = Math.floor(gap / 2)
  }
}
/**
 * @desc 希尔排序的辅助算法，就是一个基于gap的插入排序
 * @param {number[]} list
 * @param {number} gap
 */
function insertSortByGap(list, gap){
  for(let i=gap; i<list.length; i++){
    let pos = i
    let cur = list[i]
    while(pos > 0 && list[pos-gap] > cur){
      list[pos] = list[pos-gap]
      pos -= gap
    }
    list[pos] = cur
  }
}

let arr = [3, 14, 6, 4, 8, 7, 25, 9, 0, 12, 13, 24,10, 17]
shellSort(arr)
// arr: [0,  3,  4,  6,  7,  8, 9, 10, 12, 13, 14, 17, 24, 25]
console.log("arr:", arr)

归并排序

/**
 * @desc 归并排序
 * @param {number[]} list
 */
function mergeSort(list){
  if(list.length <= 1){
    return list
  }
  let mid = Math.floor(list.length / 2)
  let left = mergeSort(list.slice(0, mid))
  let right = mergeSort(list.slice(mid))
  let merged = []
  while(left && left.length>0 && right && right.length>0){
    if(left[0] < right[0]){
      merged.push(left.shift())
    }else{
      merged.push(right.shift())
    }
  }
  if(left && left.length>0){
    merged.push(...left)
  }else{
    merged.push(...right)
  }
  return merged
}
let arr = [3, 14, 6, 4, 8, 7, 25, 9, 0, 12, 13, 24,10, 17]
let newArr = mergeSort(arr)
// arr: [0,  3,  4,  6,  7,  8, 9, 10, 12, 13, 14, 17, 24, 25]
console.log("arr:", newArr)

快速排序

/**
 * @desc 快速排序入口程序
 * @param {number[]} list
 */
function quickSort(list){
  quickSortHelper(list, 0, list.length - 1)
}
/**
 * @desc 辅助程序，通过中值将列表分开分别进行快速排序
 * @param {number[]} list
 * @param {number} first 开始下标
 * @param {number} last 结束下标
 */
function quickSortHelper(list, first, last){
  if(first < last){
    let splitPoint = partition(list, first, last)
    quickSortHelper(list, first, splitPoint-1)
    quickSortHelper(list, splitPoint+1, last)
  }
}
/**
 * @desc 分裂程序，返回中值
 * @param {number[]} list
 * @param {number} first
 * @param {number} last
 * @returns {number}
 */
function partition(list, first, last){
  let pivotValue = list[first]
  let leftMark = first + 1
  let rightMark = last
  let done = false
  while(!done){
    while (leftMark <= rightMark && list[leftMark] <= pivotValue){
      leftMark += 1
    }
    while(leftMark <= rightMark && list[rightMark] >= pivotValue){
      rightMark -= 1
    }
    if(leftMark > rightMark){
      done = true
    }else{
      let cur = list[leftMark]
      list[leftMark] = list[rightMark]
      list[rightMark] = cur
    }
  }
  list[first] = list[rightMark]
  list[rightMark] = pivotValue
  return rightMark
}

let arr = [3, 14, 6, 4, 8, 7, 25, 9, 0, 12, 13, 24,10, 17]
quickSort(arr)
// arr: [0,  3,  4,  6,  7,  8, 9, 10, 12, 13, 14, 17, 24, 25]
console.log("arr:", arr)

计数排序

function countingSort(arr: number[], maxValue: number): number[] {
  let bucketLen = maxValue + 1
  let bucket = new Array(bucketLen+1).fill(0)
  let sortedIndex = 0
  let length = arr.length
  for (let i = 0; i < length; i ++) {
    bucket[arr[i]] += 1
  }

  for (let j = 0; j < bucketLen; j ++) {
    while(bucket[j] > 0) {
      arr[sortedIndex] = j
      sortedIndex += 1
      bucket[j] -= 1
    }
  }
  return arr
}