1. 1. 冒泡排序
  2. 2. 选择排序
  3. 3. 插入排序
  4. 4. 希尔排序
  5. 5. 归并排序
  6. 6. 快速排序
  7. 7. 计数排序
  8. 8. 桶排序
  9. 9. 基数排序
  10. 10. 算法可视化
【算法】排序算法总结
算法

前置函数：

1
2
3
4
5
6
// 交换位置函数
function swap (arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
function bubbleSort (arr) {
  const len = arr.length
  for (let i = 0; i < len - 1; i ++) {
    for (let j = 0; j < len - 1; j ++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
      }
    }
  }
  return arr
}

▼算法步骤：

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

▼时间复杂度：

  • 平均时间复杂度：O(n²)
  • 最好情况：数组本身是排好序的，只需要进行n - 1次比较，时间复杂度O(n)
  • 最坏情况：数组本身是逆序的，需要进行n(n-1)/2次比较，时间复杂度O(n²)

▼改进：

  • 设置标志位，如果有一趟没有发生交换（ flag = false ），说明排序已完成
  • 标记排序完成的最后位置，下次从头遍历的时候只需要遍历到这个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 改进后的冒泡
function bubbleSort (arr) {
  let len = arr.length
  let swapped
  do {
    swapped = false
    for (let i = 1; i < len; i ++) {
      if (arr[i - 1] > arr[i]) {
        swap(arr, i - 1, i)
        swapped = true
      }
    }
    len --
  } while (swapped)
  
  return arr
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function selectionSort (arr) {
  const len = arr.length
  let minIndex
  for (let i = 0; i < len - 1; i ++) {
    minIndex = i                         // minIndex始终作为最小值的位置索引
    for (let j = i + 1; j < len; j ++) { // 当前最小值的后一位开始比较
      if (arr[j] < arr[minIndex]) {    // 寻找最小的数
        minIndex = j                 // 将最小数的索引保存
      }
    }
    swap(arr, i, minIndex) // 当前轮次中的i与最小值进行交换
  }
  return arr
}

▼算法步骤：

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  • 重复第二步，直到所有元素均排序完毕

▼时间复杂度：

  • 平均时间复杂度：O(n²)
  • 最好情况：O(n²)
  • 最坏情况：O(n²)

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
function insertionSort (arr) {
  const len = arr.length
  for (let i = 1; i < len; i ++) {
    const key = arr[i]
    let j
    for (j = i - 1; (j >= 0) && (arr[j] > key); j --) {
      arr[j + 1] = arr[j] // 将数据向右移动，直到找到指定位置
    }
    arr[j + 1] = key // 将数据插入指定位置
  }
  return arr
}

▼算法步骤：

  • 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  • 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

▼时间复杂度：

  • 平均时间复杂度：O(n²)
  • 最好情况：O(n)
  • 最坏情况：O(n²)

▼算法特点：如果所要排序的数组是近乎有序的数组，则能接近于最好的情况（即完全有序的数组），算法的效率会比快排更好。

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shellSort (arr) {
  const len = arr.length
  let gap = 1
  while (gap < len / 3) { // 动态定义间隔序列
  	gap = gap * 3 + 1
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
  	for (let i = gap; i < len; i ++) { // 插入排序
      const temp = arr[i]
      let j
      for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
  return arr
}

▼算法步骤：

  • 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1
  • 按增量序列个数 k，对序列进行 k 趟排序
  • 每趟排序，根据对应的增量 ti，将待排序列分割成若干⻓度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表⻓度即为整个序列的⻓度

▼时间复杂度：

  • 平均时间复杂度：O(n^1.3)
  • 最好情况：O(n)
  • 最坏情况：O(n²)

▼算法特点：是插入排序的改进，但是插入排序是稳定的，而希尔排序是不稳定的。

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function mergeSort (arr) {
  const len = arr.length
  if (len < 2) {
    return arr
  }
  const middle = Math.floor(len / 2)
  const left = arr.slice(0, middle)
  const right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

function merge (left, right){
  let result = [] // 开辟新空间
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift()) // 把最小的最先取出，放到结果集中
    } else {
      result.push(right.shift())
    }
  }
  return result.concat(left).concat(right)
}

▼算法步骤：

  • 申请空间，使其⼤⼩为两个已经排序序列之和，该空间⽤来存放合并后的序列
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  • ⽐较两个指针所指向的元素，选择相对⼩的元素放⼊到合并空间，并移动指针到下⼀位置
  • 重复步骤 3 直到某⼀指针达到序列尾
  • 另⼀序列剩下的所有元素直接复制到合并序列尾

▼时间复杂度：

  • 平均时间复杂度：O(nlogn)
  • 最好情况：O(nlogn)
  • 最坏情况：O(nlogn)

▼算法特点：稳定性好，不论啥情况，时间复杂度都是O(nlogn)

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 普通语义化版（阮一峰），好理解，但是性能差一些
function quickSort (arr) {
  const len = arr.length
  if (len <= 1) {
    return arr
  }
  // 基准为数组中间的元素
  const pivotIndex = Math.floor(len / 2)
  const pivot = arr.splice(pivotIndex, 1)[0]
  let left = []
  let right = []
  for (let i = 0; i < len - 1; i ++) {
    // 以基准为界，分割左右区域
  	if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}
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
// 在原数组上操作的版本，比较节约空间
function partition (arr, start, end) {
  // 基准为数组的始元素
  const pivot = arr[start]
  let left = start
  let right = end + 1
  let cur = start + 1
  // 从第二个元素开始比较
  for (; cur < right; cur ++) {
    if (arr[cur] < pivot) { 
      // 如果当前元素比基数小，就和右边的大数交换，left就往右移了一位
      // 可以看出最坏的情况，相当于冒泡
      swap(arr, cur, ++ left)
    }
  }
  // 把基数放在本应属于他的位置
  swap(arr, start, left)
  return left
}

function quickSort (arr, start, end) {
  start = typeof start !== 'number' ? 0 : start
  end = typeof end !== 'number' ? arr.length - 1 : end
  if (start < end) {
  	const partitionIndex = partition(arr, start, end)
    quickSort(arr, start, partitionIndex - 1)
    quickSort(arr, partitionIndex + 1, end)
  }
  return arr
}

▼算法步骤：

  • 从数列中挑出⼀个元素，称为 “基准”（pivot）
  • 重新排序数列，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯（相同的数可以到任⼀边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
  • 递归地（recursive）把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序

▼时间复杂度：

  • 平均时间复杂度：O(nlogn)
  • 最好情况：O(nlogn)
  • 最坏情况：O(n²)

▼改进：

固定位置的基准选取会降低快排算法在面对有序数组，或者部分有序数组时的执行效率。因此我们需要修改选取基准的策略：

  • 随机基准：取待排序列中任意一个元素作为基准。一种相对安全的策略，可以降低遇到最坏情况的概率，一切看天意。
1
2
3
4
5
function randomInt (min, max) {
  return Math.round(Math.random() * (max - min)) + min
}

const pivot = arr[randomInt(start, end)]
  • 三数取中：选择三个数，然后比较取排中间的那个数。对于随机不重复的数组，有比较好的保证拆分比较均匀。对于存在重复数据的数组，则起不到作用。
1
2
3
4
5
6
7
function median (a, b, c) {
  if ((a - b) * (b - c) > 0) return b // a > b && b > c
  else if ((b - a) * (a - c) > 0) return // a b > a && a > c
  else return c
}

const pivot = median(arr[start], arr[middle] ,arr[end])
  • 三路快排：可以解决重复数据问题。
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
function partition (arr, start, end) {
  // 基准为数组的始元素
  const pivot = arr[start]
  let left = start // arr[start, left] < pivot
  let right = end + 1 // arr[right, end] > pivot
  let cur = start + 1 // arr[left + 1, i] = pivot
  // 三路的意思，是指划分了三个区域
  while (cur < right) {
    if (arr[cur] < pivot) {
      swap(arr, cur ++, ++ left)
    } else if (arr[cur] > pivot) {
      swap(arr, cur, -- right)
    } else { // arr[cur] === pivot
      cur ++
    }
  }

  swap(arr, start, left)
  return {
    pLeft: left,
    pRight: right
  }
}

function quickSortThreeWay (arr, start, end) {
  start = typeof start !== 'number' ? 0 : start
  end = typeof end !== 'number' ? arr.length - 1 : end
  if (start < end) {
  	const partitionIndex = partition(arr, start, end)
    quickSortThreeWay(arr, start, partitionIndex.pLeft - 1)
    quickSortThreeWay(arr, partitionIndex.pRight, end)
  }
  return arr
}
  • 加入插入排序：当快排分割到一定程度的时候，每个部分有序的可能性是比较大的。因此我们可以在后部分的排序中使用插入排序，这对于几乎有序的数组的排序也是很好的优化。
1
2
3
4
5
6
7
8
9
10
11
function quickSort (arr, start, end) {
  start = typeof start !== 'number' ? 0 : start
  end = typeof end !== 'number' ? arr.length - 1 : end
  if (end - start <= 15) { // 当数据小于某个规模时，使用插入排序
    insertionSort(arr, start, end)
  }
  const partitionIndex = partition(arr, start, end)
  quickSort(arr, start, partitionIndex - 1)
  quickSort(arr, partitionIndex + 1, end)
  return arr
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function countingSort (arr, maxValue) {
  // 开辟空间，maxValue表示可能存在于数组的确定最大值
  // 以分数为例，已知最高分为满分100，那么 maxValue = 100
  let bucket = new Array(maxValue + 1)
  let sortedIndex = 0
  const arrLen = arr.length
  const bucketLen = maxValue + 1
  for (let i = 0; i < arrLen; i ++) {
  	if (!bucket[arr[i]]) {
      bucket[arr[i]] = 0
    }
    bucket[arr[i]] ++
  }
  for (let j = 0; j < bucketLen; j ++) {
  	while (bucket[j] > 0) {
      arr[sortedIndex ++] = j
      bucket[j]--
    }
  }
  return arr
}

▼算法特点：

将输⼊的数据值转化为键存储在额外开辟的数组空间中。作为⼀种线性时间复杂度的排序，计数排序要求输⼊的数据必须是有确定范围的整数。计数排序是一种以空间换时间的算法。

▼时间复杂度：

  • 平均时间复杂度：O(n)
  • 最好情况：O(n)
  • 最坏情况：O(n)

▼空间复杂度：O(maxValue)

桶排序

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
function bucketSort (arr, bucketSize = 5) {
  // 生成一个bucketSize * bucketSize的数组空间
  const buckets = [...new Array(bucketSize)].map(() => [])
  const max = Math.max(...arr)
  
  for (let i = 0; i < arr.length; i ++) {
    const number = arr[i]
    const bucketIndex = Math.floor(number / (max + 1) * bucketSize) // 映射函数
    const bucket = buckets[bucketIndex]
    bucket.push(number)

    let j = bucket.length - 1
    // 对加进桶内的元素排序 这里的排序是普通的冒泡
    while (j > 0 && bucket[j - 1] > bucket[j]) {
      swap(bucket, j - 1, j)
      j --
    }
  }
  
  let i = 0
  for (let bucketIndex = 0; bucketIndex < bucketSize; bucketIndex ++) {
    const bucket = buckets[bucketIndex]
    for (let j = 0; j < bucket.length; j ++) {
      arr[i] = bucket[j] // 将元素从每个桶中取出
      i ++
    }
  }
  return arr
}

桶排序是计数排序的升级版。它利⽤了函数的映射关系，⾼效与否的关键就在于这个映射函数的确定。为了使桶排序更加⾼效，我们需要做到这两点：

  • 在额外空间充⾜的情况下，尽量增⼤桶的数量
  • 使⽤的映射函数能够将输⼊的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种⽐较排序算法对于性能的影响⾄关重要。

▼算法特点：

桶排序是所有排序算法中最快的一种，但是它所耗费的空间也是最多的。

基数排序

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
function radixSort (arr) {
  const max = Math.max(...arr)
  // 通过Array.from新建一个长度为10的二维数组
  const buckets = Array.from({ length: 10 }, () => [])

  let m = 1
  while (m < max) {
    for (let i = 0; i < arr.length; i ++) {
      const number = arr[i]
      // digit表示某位数的值
      // ~~ === Math.floor
      const digit = ~~((number % (m * 10)) / m)
      // 把该位数的值放到桶buckets中
      // 通过索引确定顺序 类比计数排序
      buckets[digit].push(number)
    }

    let i = 0
    for (let bucketIndex = 0; bucketIndex < buckets.length; bucketIndex ++) {
      const bucket = buckets[bucketIndex]
      while (bucket.length > 0) {
        // shift从头部取值
        // 保证按照队列先入先出
        arr[i ++] = bucket.shift()
      }
    }
    // 每次最外层while循环后m要乘等10
    // 也就是要判断下一位 比如当前是个位 下次就要判断十位
    m *= 10
  }

  return arr
}

▼算法特点：

  • 是一种非比较的排序，是计数排序的进阶版
  • 按照相同位有效数字的值分组排序
  • 有桶的概念，通过一个桶从右至左按照每一位的大小依次进行排序
  • 每一位的排序都遵循队列进行先入先出重新写入

▼时间复杂度：O(nlog(r)m)，其中r为所采取的基数，而m为堆数

算法可视化

一些算法可视化项目，能更好的get到这些算法的过程和思想：

Previous post
Next post