JavaScript 算法初探

Posted on Edited on In

https://www.jianshu.com/p/1b4068ccd505
http://louiszhai.github.io/2016/12/23/sort/

排序算法

冒泡排序

基数排序


双重多循环，按位循环匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function radixSort(arr, maxDigit) {
	var counter = []
  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 = ~~((arr[j] % mod) / dev)
      if(counter[bucket]==null) {
        counter[bucket] = []
      }
      counter[bucket].push(arr[j])
    }
    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;
}
var sorts = [23, 10000000, 31, 11, 1, 2, 4]
radixSort(sorts, 8)

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function radixSort(arr) {
	var counter = []
	var maxDigit = Math.max(...arr).toString().length
	for (var i = 0; i < maxDigit; i++) {
		var reg = RegExp("^\\d*(\\d)\\d{" + i + "}$")
		arr.forEach((item) => {
			var bucket = 0
			item.toString().replace(reg, ($0, $1) => {
				bucket = $1
			})
			if (counter[bucket] == undefined) counter[bucket] = []
			counter[bucket].push(item)
		})
		var pos = 0
		counter.forEach((item) => {
			var value = null
			if (item != null) {
				while ((value = item.shift()) != null) {
					arr[pos++] = value
				}
			}
		})
	}
	return arr
}
var sorts = [23, 10000000, 31, 11, 1, 2, 4]
radixSort(sorts, 8)

通过正则判断不同位置的数值，默认为0。

各种排序性能对比如下:

排序类型平均情况最好情况最坏情况辅助空间稳定性
冒泡排序O(n²)O(n)O(n²)O(1)稳定
选择排序O(n²)O(n²)O(n²)O(1)不稳定
直接插入排序O(n²)O(n)O(n²)O(1)稳定
折半插入排序O(n²)O(n)O(n²)O(1)稳定
希尔排序O(n^1.3)O(nlogn)O(n²)O(1)不稳定
归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)稳定
快速排序O(nlog₂n)O(nlog₂n)O(n²)O(nlog₂n)不稳定
堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)不稳定
计数排序O(n+k)O(n+k)O(n+k)O(k)稳定
桶排序O(n+k)O(n+k)O(n²)O(n+k)(不)稳定
基数排序O(d(n+k))O(d(n+k))O(d(n+kd))O(n+kd)稳定