基本排序算法-插入、选择、冒泡排序

发表于 分类于

插入排序

特点：

  1. 所需时间受输入元素初始顺序的影响
  2. 如果数据是局部有序的，那么用插入排序会很高效。
  3. 也很适合小规模数组，在V8引擎里调用Array.prototype.sort()时，当数组长度大于10个的情况下，采用的是快速排序，而当长度小于等于10个时则切换为插入排序，以提高运算效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * @Description: insertSort
 * @Author: libk
 * @Github: https://github.com/libk
 */
function insertSort (arr) {
  if (arr === null || arr === undefined || arr.length < 2) {
    return
  }

  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
      }
    }
  }
}

选择排序

特点：

  1. 运行时间和输入数据的特征无关，只与数据的规模有关
  2. 数据移动是最少的，只有N次数据交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * @Description: selectionSort 
 * @Author: libk
 * @Github: https://github.com/libk
 */
function selectionSort (arr) {
  if (arr === null || arr === undefined || arr.length < 2) {
    return
  }

  for (let i = 0; i < arr.length; i++) {
    let min = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j
      }
    }
    if (min !== i) {
      [arr[i], arr[min]] = [arr[min], arr[i]]
    }
  }
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * @Description: bubbleSort
 * @Author: libk
 * @Github: https://github.com/libk
 */
function bubbleSort (arr) {
  if (arr === null || arr === undefined || arr.length < 2) {
    return
  }
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
}