十大经典排序算法

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	In-place	稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	In-place	不稳定
插入排序	O(n2)	O(n)	O(n2)	O(1)	In-place	稳定
希尔排序	O(n log n)	O(n log2 n)	O(n log2 n)	O(1)	In-place	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	Out-place	稳定
快速排序	O(n log n)	O(n log n)	O(n2)	O(log n)	In-place	稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	In-place	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-place	稳定
桶排序	O(n+k)	O(n+k)	O(n2)	O(n+k)	Out-place	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	Out-place	稳定

1.冒泡排序 ok

冒泡排序：前一项和后一项比较，当前的大于后一项，交换位置。

相邻左右比较一边，把大的防到右边，第一轮完成后，最右边是这个数组中最大的一个了；

接着比较除了最右边的其他元素，循环往复；

1.一般形式

let targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
let bubbleSort = (params) => {
  for (let i = 0; i < params.length - 1; i++) {
    for (let j = 0; j < params.length - 1 - i; j++) {
      let preValue = params[j]
      let nextValue = params[j + 1]
      if (preValue > nextValue) {
        params[j + 1] = preValue
        params[j] = nextValue
      }
    }
  }
  return params
}
console.log(bubbleSort(targetValue))

2.优化

可能提前已经排好序了，所以可以用一个变量判断是否排好序，排好序后里面遍历不会交换元素

let targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
let bubbleSort = (params) => {
  let onoff = true
  for (let i = 0; i < params.length - 1; i++) {
    for (let j = 0; j < params.length - 1 - i; j++) {
      let preValue = params[j]
      let nextValue = params[j + 1]
      if (preValue > nextValue) {
        onoff = true
        params[j + 1] = preValue
        params[j] = nextValue
      }
    }
    if (onoff) {
      onoff = false
    } else {
      break
    }
  }
  return params
}
console.log(bubbleSort(targetValue))

2.选择排序 ok

选择排序：把每一个数都与第一个数比较，如果小于第一个数，就把他们交换位置；这样一轮下来最小的数就排在了最前面；重复 n-1 轮就实现了排序

1.普通模式

let targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
let selectSort = (params) => {
  let minIndex
  for (let i = 0; i < params.length; i++) {
    minIndex = i
    let minVal = params[minIndex]
    for (let j = i + 1; j < params.length; j++) {
      let nextVal = params[j]
      if (minVal > nextVal) {
        params[minIndex] = nextVal
        params[j] = minVal
      }
    }
  }
  return params
}
console.log(selectSort(targetValue))

3.插入排序 ok

插入排序

let targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
let insertSort = (params) => {
  for (let i = 1; i < params.length; i++) {
    let currentVal = params[i],
      len = i - 1
    while (len >= 0 && params[len] > currentVal) {
      params[len + 1] = params[len]
      len--
    }
    params[len + 1] = currentVal
  }
  return params
}
console.log(insertSort(targetValue))

4.希尔排序

希尔排序：

function shellSort(arr) {
  var len = arr.length,
    temp,
    gap = 1
  while (gap < len / 3) {
    //动态定义间隔序列
    gap = gap * 3 + 1
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i]
      for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
  return arr
}

5.归并排序 ok

归并排序：

let targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
let mergeSort = (params) => {
  if (params.length <= 1) return params
  let middlePoint = (params.length / 2) | 0
  let left = params.slice(0, middlePoint)
  let right = params.slice(middlePoint, params.length)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  let result = []
  while (left.length && right.length) {
    left[0] > right[0] ? result.push(right.shift()) : result.push(left.shift())
  }
  while (left.length) {
    result.push(left.shift())
  }
  while (right.length) {
    result.push(right.shift())
  }
  return result
}
console.log(mergeSort(targetValue))

6.快速排序 ok

快速排序：首先从中间分割成两部分，左边放大的，中间放分割的那个数，右边放小的；左边和右边的数组重复上述循环。

let targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
let quickSort = (params) => {
  if (params.length <= 1) return params
  let point,
    left = [],
    right = []
  point = (params.length / 2) | 0
  let pointVal = params.splice(point, 1)[0]
  params.forEach((item) => {
    item > pointVal ? right.push(item) : left.push(item)
  })

  return [...quickSort(left), pointVal, ...quickSort(right)]
}
console.log(quickSort(targetValue))

7.堆排序

堆排序:

var len // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {
  // 建立大顶堆
  len = arr.length
  for (var i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i)
  }
}

function heapify(arr, i) {
  // 堆调整
  var left = 2 * i + 1,
    right = 2 * i + 2,
    largest = i

  if (left < len && arr[left] > arr[largest]) {
    largest = left
  }

  if (right < len && arr[right] > arr[largest]) {
    largest = right
  }

  if (largest != i) {
    swap(arr, i, largest)
    heapify(arr, largest)
  }
}

function swap(arr, i, j) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function heapSort(arr) {
  buildMaxHeap(arr)

  for (var i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i)
    len--
    heapify(arr, 0)
  }
  return arr
}

8.计数排序 ok

计数排序:

let targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
let countSort = (params, maxVal) => {
  let bucket = new Array(maxVal + 1),
    sort = 0
  params.forEach((item) => {
    bucket[item] ? bucket[item]++ : (bucket[item] = 1)
  })
  bucket.forEach((item, index) => {
    while (item) {
      params[sort] = index
      sort++
      item--
    }
  })
  return params
}

console.log(countSort(targetValue, 72))

9 桶排序

桶排序:

function bucketSort(arr, bucketSize) {
  if (arr.length === 0) {
    return arr
  }

  var i
  var minValue = arr[0]
  var maxValue = arr[0]
  for (i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i] // 输入数据的最小值
    } else if (arr[i] > maxValue) {
      maxValue = arr[i] // 输入数据的最大值
    }
  }

  //桶的初始化
  var DEFAULT_BUCKET_SIZE = 5 // 设置桶的默认数量为5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE
  var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
  var buckets = new Array(bucketCount)
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = []
  }

  //利用映射函数将数据分配到各个桶中
  for (i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i])
  }

  arr.length = 0
  for (i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]) // 对每个桶进行排序，这里使用了插入排序
    for (var j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j])
    }
  }

  return arr
}

10.基数排序 ok

基数排序:

var targetValue = [1, 2, 3, 4, 56, 6, 72, 3, 54, 56]
var counter = []
let radixSort = function (arr, maxDigit) {
  var mod = 10;
  var dev = 1
  for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    for (var j = 0; j < arr.length; j++) {
      var bucket = parseInt((arr[j] % mod) / dev)
      console.log(bucket, j)
      if (counter[bucket] == null) {
        counter[bucket] = []
      }
      counter[bucket].push(arr[j])
    }
    console.log(counter, 77777777)
    var pos = 0
    for (var j = 0; j < counter.length; j++) {
      var value = null
      if (counter[j] != null) {
        while ((value = counter[j].shift()) != null) {
          arr[pos++] = value
        }
      }
    }
  }
  return arr
}
console.log(radixSort(targetValue, 2))
}