排序算法

2016-09-05 数据结构与算法

冒泡排序

外循环控制几轮冒泡，内循环进行冒泡（比较大小交换位置，就像气泡一样从数组底部”冒泡”到数组的顶部）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort(arr) {
  const len = arr.length
  // 共进行 arr.length 轮冒泡
  for (let i = 0; i < len; i++) {
    // 冒泡
    // 俩俩对比，最后一个元素后面没有元素了，所以减 1，已冒泡上去的元素无需再参与，所以减 i
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // distribute 交换数组位置
      }
    }
  }

  return arr
}

bubbleSort([3, 44, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48])

注：在 Array 原型链上扩展。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Array.prototype.bubbleSort = function () {
  for (var i = 0; i < this.length; i++) {
    for (var j = 0; j < this.length - i - 1; j++) {
      if (this[j] - this[j + 1] > 0) {
        temp = this[j]
        this[j] = this[j + 1]
        this[j + 1] = temp
      }
    }
  }

  return this
}

[3, 44, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].bubbleSort()

快速排序

快速排序从冒泡排序演变而来，也是交换排序，但比冒泡排序高效。快速排序基于分治策略，通过选择一个基准元素将数组分成两个子数组，然后递归地对子数组进行排序。

以第一个元素为基准元素：

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
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }

  // 将第一个元素为基准元素
  const pivot = arr[0]
  const left = []
  const right = []

  // 将小于基准的元素放入 left 数组，大于基准的元素放入 right 数组
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  // 递归排序左右子数组
  const sortedLeft = quickSort(left)
  const sortedRight = quickSort(right)

  // 返回排好序的数组：left + 基准 + right
  return sortedLeft.concat(pivot, sortedRight)
}

quickSort([3, 44, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48])

以任意元素为基准元素：

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
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }

  // 选择任意元素为基准元素
  const pivotIndex = Math.floor(Math.random() * arr.length)
  const pivot = arr[pivotIndex]
  const left = []
  const right = []

  // 将小于基准的元素放入 left 数组，大于基准的元素放入 right 数组
  // 基准值是任意的，所以从 0 开始遍历，然后将基准值忽略即可
  for (let i = 0; i < arr.length; i++) {
    if (i !== pivotIndex) {
      if (arr[i] < pivot) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
  }

  // 递归排序左右子数组
  const sortedLeft = quickSort(left)
  const sortedRight = quickSort(right)

  // 返回排好序的数组：left + 基准 + right
  return sortedLeft.concat(pivot, sortedRight)
}

quickSort([3, 44, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48])

插入排序

插入排序是一种简单的排序算法，其基本思想是将数组分为两部分，已排序部分和未排序部分，且以数组第一项为默认已排序项，然后逐步将未排序部分的元素插入到已排序部分的适当位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertionSort(arr) {
  const n = arr.length
  for (let i = 1; i < n; i++) {
    let j = i
    // 存在上一项，且当前项小于上一项，则交互位置
    // j-- 目的是为了将当前项与所有的已排项进行对比
    while (j - 1 >= 0 && arr[j] < arr[j - 1]) {
      const temp = arr[j]
      arr[j] = arr[j - 1]
      arr[j - 1] = temp
      // 继续往前插入
      j--
    }
  }
  return arr
}

insertionSort([3, 44, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48])