排序算法

Posted on | In ,

冒泡排序

每次交换两个元素的位置，一直交换到最大/最小的元素到了最前面/后面。下次循环舍弃掉这个元素的位置，继续交换一轮。
好处是可以设置一个标识，比如我的代码里的swap。如果一个循环之后没有交换位置，就意味着此时的允许已经正确了，不需要继续循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bubble(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swap = false
    for (j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap = true
        let tmp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
      }
    }
    if (!swap) {
      console.log('!swap')
      break
    }
  }
  return arr
}

平均时间复杂度O(n²)，最好情况O(n)，最坏情况O(n²)，空间复杂度O(1)。

选择排序

直接找出最大/最小的值，与最后/最前一个值交换。下次循环舍弃这个位置，继续找出最大/最小的值，交换。
直观容易理解，但哪怕已经排序完成仍旧需要继续走完全部的流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function select(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min = Infinity,
      minIndex = 0
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < min) {
        min = arr[j]
        minIndex = j
      }
    }
    let tmp = arr[minIndex]
    arr[minIndex] = arr[i]
    arr[i] = tmp
  }
  return arr
}

时间复杂度最好最坏都是O(n²)，空间复杂度O(1)。

插入排序

直接插入排序

将待排序的元素插入到排好序的部分中，直到所有元素都插入进去。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function directInsertion(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i],
      j = i - 1
    while (j >= 0 && current < arr[j]) {
      arr[j + 1] = arr[j]
      j--
    }
    if (j + 1 !== i) {
      arr[j + 1] = current
    }
  }
  return arr
}
```  

当前元素比第j个小，第j个元素就往后移。如果不比第j个小，那么空位就是当前的j+1。
时间复杂度：平均O(n²)，最好O(n)，最坏O(n²)。空间复杂度O(1)。

### 快速排序

每次寻找一个基点，把比基点小的放在左边，大的放在右边，然后对左边和右边的数组重复以上操作。

``` JavaScript
function quick(arr) {
  if (arr.length <= 1) {
    return arr
  }
  let left = [],
    right = []
  let baseIndex = Math.floor(arr.length / 2),
    base = arr.splice(baseIndex, 1)[0]
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < base) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quick(left).concat([base], quick(right))
}