编程语言有很多，但是算法都是通用的，下面以JavaScript为例介绍几种简单的排序算法

一，时间复杂度

学算法前当然是先要了解什么是时间复杂度，说白了就是运行完一段代码所要花费的时间，再直白点可以理解为这段代码一共执行了几句

图中O(N)和n成线性关系，N的变化倍率和时间变化倍率成正比。

由图可以看出：O(N^N) >> O(2^N) >> O(N^3) >> O(N^2) >> O(N * lnN)

也就是说O(N*lnN)的时间复杂度是最小的，在写算法时我们就是为了追求更小的时间复杂度才有了各种各样的算法和数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 3n => O(N)
let n = 100
for(let i = 0;i < n;i++){
    let a = 3;
    // 300 次
}

// 4n => O(N)
for(let i = 0;i < n;i++){
    let a = 3;
    let b = 2 
}

// O(N)*O(N) => O(N^2)
for(let i = 0;i < n;i++){
    for(let j = 0;j < n;j++){
        let a = 3
   	}
}

二，选择排序

思路：遍历整个数组，找出最大/最小的数，将找出的数从当前数组删除并将这个数添加到一个新的数组中，如此反复知道数组里的元素全部移到新的数组里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const _selectSort = (arr) => {
    let newArr = []
    for (let i = 0; i < arr.length; i++) {
        var index = i
        var min = arr[i]
        for (let j = i; j < arr.length - 1; j++) {
            if (min > arr[j]) {
                min = arr[j]
                index = j
            }
        }
        arr.splice(index, 1)
        newArr.push(min)
    }
    return newArr
}

另一种写法，思路一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const _chooseSort = (arr) => {
    let newArr = []
    while (arr.length) {
        var min = arr[0];
        var i = 0
        arr.forEach((item, index) => {
            if (min > item) {
                min = item
                i = index
            }
        })
        arr.splice(i, 1)
        newArr.push(min)
    }
    return newArr
}

无论是那种写法都不可避免的要使用两层for循环，所以选择排序的时间复杂度为O(N^2)

三，冒泡排序

思路：遍历对比前一个和后一个数，如果后一个数小于前一个数就交换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const _bubbleSort = (arr) => {
    for (let j = 0; j < arr.length; j++) {
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                let temp = arr[i]
                arr[i] = arr[i + 1]
                arr[i + 1] = temp
                // es6 方法能快速交换两个数的位置
                [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
            }
        }
    }
    return arr
}

这里也用了两层for循环，所以时间复杂度也为O(N^2)

四，快速排序

思路：找出一个中间数将小于中间数的数放到左边，大于中间数的数放到右边，递归调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const _qSort = (arr) => {
    function qs(arr,left,right){
        let l = left
        let r = right
        if(l > r) return
        while(l != r){
            while(arr[l] <= arr[r] && l < r){
                l++
            }
            [arr[l], arr[r]] = [arr[r], arr[l]]
            while(arr[l] <= arr[r] && l < r){
                r--
            }
            [arr[l], arr[r]] = [arr[r], arr[l]]
        }
        let middle = r
        qs(arr, left, middle - 1)
        qs(arr, middle + 1, right)
    }
    qs(arr,0,arr.length - 1)
}

另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const _qSort2 = (arr) => {
    if (arr.length <= 1) return arr;
    let middleIndex = Math.floor(arr.length / 2)
    let middle = arr.splice(middleIndex, 1)[0]
    let left = []
    let right = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < middle) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return _qSort2(left).concat([middle], _qSort2(right))
}

这里的时间复杂度为O(NlnN)

以上就是几种简单的算法了，在数据足够多是快速排序是明显比其他算法快不少的

下次更新二叉搜索树的实现