经典排序算法的 JS 实现

tao

发布于2021-08-14 | 更新于2023-12-29

冒泡排序

function sort(array){
  for(var i = 0; i < array.length - 1; i++){
    for(var j = 0; j < array.length - i - 1; j++){
      if(array[j] > array[j+1]){
        var temp = array[j+1]
        array[j+1] = array[j]
        array[j] = temp
      }
    }
  }
}

var array = [5, 8, 6, 3, 9, 2, 1, 7]
sort(array)
console.log(array)
// [1, 2, 3, 5, 6, 7, 8, 9]

冒泡排序优化

function sort(array){
  for(var i = 0; i < array.length - 1; i++){
    var isSorted = true

    for(var j = 0; j < array.length - i - 1; j++){
      if(array[j] > array[j+1]){
        var temp = array[j+1]
        array[j+1] = array[j]
        array[j] = temp
        isSorted = false
      }
    }

    if(isSorted){
      break
    }
  }
}

var array = [5, 8, 6, 3, 9, 2, 1, 7]
sort(array)
console.log(array)
// [1, 2, 3, 5, 6, 7, 8, 9]

冒泡排序继续优化

function sort(array){
  var lastExchangeIndex = 0
  var sortBorder = array.length - 1

  for(var i = 0; i < array.length - 1; i++){
    var isSorted = true

    for(var j = 0; j < sortBorder; j++){
      if(array[j] > array[j+1]){
        var temp = array[j+1]
        array[j+1] = array[j]
        array[j] = temp
        isSorted = false
        lastExchangeIndex = j
      }
    }

    sortBorder = lastExchangeIndex

    if(isSorted){
      break
    }
  }
}

var array = [3, 4, 2, 1, 5, 6, 7, 8]
sort(array)
console.log(array)
// [1, 2, 3, 4, 5, 6, 7, 8]

鸡尾酒排序

function sort(){
  var temp

  for(var i = 0; i < array.length/2; i++){
    var isSorted = true

    for(var j = i; j < array.length - i - 1; j++){
      if(array[j] > array[j+1]){
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp
        isSorted = false
      }
    }

    if(isSorted){
      break
    }

    isSorted = true

    for(var j = array.length - i - 1; j > i; j--){
      if(array[j] < array[j - 1]){
        temp = array[j]
        array[j] = array[j-1]
        array[j-1] = temp
        isSorted = false
      }
    }

    if(isSorted){
      break
    }
  }
}

var array = [2, 3, 4, 5, 6, 7, 8, 1]
sort(array)
console.log(array)
// [1, 2, 3, 4, 5, 6, 7, 8]

插入排序

function insertionSort(arr){
  for(var i = 1; i < arr.length; i++){
    var current = arr[i]
    var preIndex = i - 1

    while(preIndex >= 0 && arr[preIndex] > current){
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }

    arr[preIndex + 1] = current
  }

  return arr
}

var array = [3, 4, 2, 1, 5, 6, 7, 8]
console.log(insertionSort(array))
// [1, 2, 3, 4, 5, 6, 7, 8]

快速排序

快速排序双边循环

function partition(arr, startIndex, endIndex){
  var pivot = arr[startIndex]
  var left = startIndex
  var right = endIndex

  while(left != right){
    while(left < right && arr[right] > pivot){
      right--
    }
    while(left < right && arr[left] <= pivot){
      left++
    }
    if(left < right){
      var p = arr[left]
      arr[left] = arr[right]
      arr[right] = p
    }
  }

  arr[startIndex] = arr[left]
  arr[left] = pivot

  return left
}

function quickSort(arr, startIndex, endIndex){
  if(startIndex >= endIndex){
    return
  }

  var pivotIndex = partition(arr, startIndex, endIndex)
  quickSort(arr, startIndex, pivotIndex - 1)
  quickSort(arr, pivotIndex + 1, endIndex)
}

var arr = [4, 4, 6, 5, 3, 2, 8, 1]
quickSort(arr, 0, arr.length - 1)
console.log(arr)
// [1, 2, 3, 4, 4, 5, 6, 8]

快速排序单边循环

function partitionV2(arr, startIndex, endIndex){
  var pivot = arr[startIndex]
  var mark = startIndex

  for(var i = startIndex; i <= endIndex; i++){
    if(arr[i] < pivot){
      mark++
      var p = arr[mark]
      arr[mark] = arr[i]
      arr[i] = p
    }
  }

  arr[startIndex] = arr[mark]
  arr[mark] = pivot
  return mark
}

function quickSort(arr, startIndex, endIndex){
  if(startIndex >= endIndex){
    return
  }

  var pivotIndex = partitionV2(arr, startIndex, endIndex)
  quickSort(arr, startIndex, pivotIndex - 1)
  quickSort(arr, pivotIndex + 1, endIndex)
}

var arr = [4, 4, 6, 5, 3, 2, 8, 1]
quickSort(arr, 0, arr.length - 1)
console.log(arr)
// [1, 2, 3, 4, 4, 5, 6, 8]

快速排序非递归

function quickSort(arr, startIndex, endIndex){
  var quickSortStack = []
  var rootParam = {}
  rootParam.startIndex = startIndex
  rootParam.endIndex = endIndex
  quickSortStack.push(rootParam)

  while(quickSortStack.length){
    var param = quickSortStack.pop()
    var pivotIndex = partitionV2(arr, param.startIndex, param.endIndex)
    if(param.startIndex < pivotIndex - 1){
      var leftParam = {}
      leftParam.startIndex = param.startIndex
      leftParam.endIndex = pivotIndex - 1
      quickSortStack.push(leftParam)
    }
    if(pivotIndex + 1 < param.endIndex){
      var rightParam = {}
      rightParam.startIndex = pivotIndex + 1
      rightParam.endIndex = param.endIndex
      quickSortStack.push(rightParam)
    }
  }
}

var arr = [4, 4, 6, 5, 3, 2, 8, 1]
quickSort(arr, 0, arr.length - 1)
console.log(arr)
// [1, 2, 3, 4, 4, 5, 6, 8]

冒泡排序的时间复杂度为O(n^2)。快速排序的平均时间复杂度为O(nlogn)，当临界值的选取刚好是最大或者最小值，这种最坏情况下的时间复杂度为O(n^2)。

堆排序

function downAdjust(array, parentIndex, length){
  var temp = array[parentIndex]
  var childIndex = 2 * parentIndex + 1
  while(childIndex < length){
    if(childIndex + 1 < length && array[childIndex + 1] > array[childIndex]){
      childIndex++
    }
    if(temp >= array[childIndex]) break
    array[parentIndex] = array[childIndex]
    parentIndex = childIndex
    childIndex = 2 * childIndex + 1
  }
  array[parentIndex] = temp
}

function heapSort(arr){
  for(var i = parseInt((arr.length - 2)/2); i >= 0; i--){
    downAdjust(arr, i, arr.length)
  }

  console.log(arr)
  // [10, 9, 8, 6, 5, 7, 2, 3, 1, 0]

  for(var i = arr.length - 1; i > 0; i--){
    var temp = arr[i]
    arr[i] = arr[0]
    arr[0] = temp
    downAdjust(arr, 0, i)
  }
}

var arr = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0]
heapSort(arr)
console.log(arr)
// [0, 1, 2, 3, 5, 6, 7, 8, 9, 10]

相较于快速排序，堆排序的时间复杂度稳定在O(nlogn)，而且没有开辟额外的空间，空间复杂度为O(1)，快速排序的空间复杂度为O(logn)。他们都是不稳定排序。

计数排序

function countSort(arr){
  var max = arr[0]
  for(var i = 1; i < arr.length; i++){
    if(arr[i] > max){
      max = arr[i]
    }
  }

  var countArray = new Array(max + 1).fill(0)
  
  for(var i = 0; i < arr.length; i++){
    countArray[arr[i]]++
  }

  console.log(countArray)
  // [1, 1, 1, 1, 2, 2, 2, 1, 1, 0, 1]

  var index = 0
  var sortedArray = []
  
  for(var i = 0; i < countArray.length; i++){
    for(var j = 0; j < countArray[i]; j++){
      sortedArray[index++] = i
    }
  }
  return sortedArray
}

var arr = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10]
console.log(countSort(arr))
// [0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 10]

计数排序优化

function countSort(arr){
  var max = arr[0]
  var min = arr[0]

  for(var i = 0; i < arr.length; i++){
    if(arr[i] > max){
      max = arr[i]
    }
    if(arr[i] < min){
      min = arr[i]
    }
  }

  var d = max - min
  var countArray = new Array(d + 1).fill(0)

  for(var i = 0; i < arr.length; i++){
    countArray[arr[i] - min]++
  }

  for(var i = 1; i < countArray.length; i++){
    countArray[i] += countArray[i - 1]
  }

  console.log(countArray)
  // [1, 3, 4, 5, 6, 7, 7, 7, 8, 10]

  var sortedArray = []
  for(var i = arr.length - 1; i >= 0; i--){
    sortedArray[countArray[arr[i] - min] - 1] = arr[i]
    countArray[arr[i] - min]--
  }

  return sortedArray
}

var arr = [95, 94, 91, 98, 99, 90, 99, 93, 91, 92]
console.log(countSort(arr))
// [90, 91, 91, 92, 93, 94, 95, 98, 99, 99]

优化后的计数排序是稳定排序，时间复杂度为O(n+m)，空间复杂度为O(m)，但是计数排序有它的局限性，当数列最大值和最小值差距过大时，不适合用计数排序，数列元素不是整数时，也不适合用计数排序。

桶排序

function bucketSort(arr){
  var max = arr[0]
  var min = arr[0]

  for(var i = 0; i < arr.length; i++){
    if(arr[i] > max){
      max = arr[i]
    }
    if(arr[i] < min){
      min = arr[i]
    }
  }

  var d = max - min
  var bucketNum = arr.length
  var bucketList = Array.from(new Array(bucketNum), () => [])
  for(var i = 0; i < arr.length; i++){
    var num = parseInt(((arr[i] - min) * (bucketNum - 1)) / d)
    bucketList[num].push(arr[i])
  }

  for(var i = 0; i < bucketList.length; i++){
    bucketList[i].sort()
  }

  console.log(bucketList)
  /*
    0: [0.0023]
    1: (2) [2.13, 3]
    2: [4.12]
    3: [6.421]
    4: [8.1]
    5: []
    6: [10.09]
  */

  var sortedArray = []
  var index = 0
  for(var i = 0; i < bucketList.length; i++){
    for(var j = 0; j < bucketList[i].length; j++){
      sortedArray[index++] = bucketList[i][j]
    }
  }

  return sortedArray
}

var arr = [4.12, 6.421, 0.0023, 3.0, 2.13, 8.1, 10.09]
console.log(bucketSort(arr))
// [0.0023, 2.13, 3, 4.12, 6.421, 8.1, 10.09]

桶排序平均时间复杂度为O(n)，性能不稳定，如果元素分布极不均匀，时间复杂度会降到O(nlogn)，空间复杂度为O(n)。

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定排序
冒泡排序	O(n^2)	O(n^2)	O(1)	稳定
插入排序	O(n^2)	O(n^2)	O(1)	稳定
快速排序	O(nlogn)	O(n^2)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定
计数排序	O(n+m)	O(n+m)	O(m)	稳定
堆排序	O(n)	O(nlogn)	O(n)	稳定