# 数组排序算法

# 冒泡排序

冒泡排序(从小到大)
把相邻两个元素两两比较,当一个元素大于右侧相邻元素,交换位置
当一个元素小于或等于由于相邻元素,位置不变
时间复杂度:要遍历所有的元素,总共遍历 元素格式 - 1 轮 => 时间复杂度 O(n^2)
稳定排序 => 相等的元素位置不会变

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      let temp
      if (arr[j] > arr[j + 1]) { // 前一项大于后一项 -> 交换位置
        temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13

冒泡排序的优化
可能在经过一定次数的排序之后数组已经有序了
但是因为外层循环的控制排序还会继续,当遇到已经排好序的情况要提前退出循环

function bubbleSortBetter(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let isSorted = true // 每一轮初始为有序
    for (let j = 0; j < arr.length - i - 1; j++) {
      let temp
      if (arr[j] > arr[j + 1]) {
        temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        // 如果有交换,说明不是有序的
        isSorted = false
      }
    }
    if (isSorted) { // 如果是有序的,退出循环
      break
    }
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 选择排序

选择排序(从小到大)
首先在未排序序列中找到最小值,放在排序序列的起始位置
然后,在从剩下未排序元素中继续寻找最小值,然后放在已排序序列的末尾
时间复杂度:O(n^2)
一共经历了 n + n-1 + n-2 + … + 2 + 1 = n * (n+1) / 2 = 0.5 * n ^ 2 + 0.5 * n

function selectSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i // 初始化最小值为未排序元素中的第一个
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) { // 从剩下的元素中找到最小值
        min = j
      }
    }
    if (min !== i) { // 最小值下标变化了,说明要进行交换
      let temp = arr[min]
      arr[min] = arr[i]
      arr[i] = temp
    }
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 插入排序

插入排序(从小到大)
将第一个元素视为有序序列,遍历数组,将之后的元素依次插入这个构建的有序序列中

  1. 从第一个元素开始,讲第一个元素视为有序
  2. 取出下一个元素,在已排序的元素中从后向前扫描
  3. 如果有序序列中的元素大于新元素,把该元素向后挪一个位置
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j + 1] < arr[j]) {
        temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
      } else {
        break
      }
    }
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 快速排序

快速排序(从小到大)
使用分治的思想把一个数组分成两个部分

  1. 选择一个元素作为基准
  2. 小于基准的元素,移动到基准的左边,大于基准的元素,移动到基准的右边
  3. 对基准左右两边分好的两个部分,重复第一步和第二步,直到所有的子集只剩下一个元素为止
  • 需要额外的空间用来储存左右子集
function quickSort(arr) {
  if (arr.length <= 1) return arr
  let pivotIndex = Math.floor(arr.length >> 1) // 数组中间元素的下标
  let pivot = arr.splice(pivotIndex, 1)[0] // 中间元素
  let left = [],
    right = []
  for (let i = 0; i < arr.length; i++) {
    let element = arr[i]
    if (element < pivot) {
      left.push(element)
    } else {
      right.push(element)
    }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  • 原地快速排序
function quickSortInPlace(arr) {
  // 交换元素
  function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }

  function partition(arr, left, right) {
    let pivot = arr[left]
    let storeIndex = left

    for (let i = left + 1; i <= right; i++) {
      if (arr[i] < pivot) {
        swap(arr, ++storeIndex, i)
      }
    }
    swap(arr, left, storeIndex)
    return storeIndex
  }
  
  function sort(arr, left, right) {
    if (left < right) {
      let storeIndex = partition(arr, left, right)
      sort(arr, left, storeIndex - 1)
      sort(arr, storeIndex + 1, right)
    }
  }

  sort(arr, 0, arr.length - 1)
  return arr
}
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
Last Updated: 5/6/2020, 11:48:16 AM