排序算法 - JavaScript

1. 选择排序

核心思想：在未排序的序列中找到最小（大）的元素，存放到排序序列的起始位置，然后再从剩余未排序的元素中继续寻找最小（大）的元素，然后放到已排序序列的末尾，以此类推，直到所有元素排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function selectionSort(arr) {
  if (!arr || arr.length < 2) return arr

  let min = 0
  const N = arr.length - 1

  for (let i = 0; i < N; i++) {
    min = i
    for (let j = i + 1; j <= N; j++) {
      min = arr[j] < arr[min] ? j : min
    }
    const [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]
  }
  return arr
}

2. 冒泡排序

核心思想：比较相邻的两个元素，比较完成视情况交换位置，一轮下来，一个元素排序好，依次类推，直到排序完成。

  • 普通版 从前到后对比

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function bubbleSort(arr) {
      if (!arr || arr.length < 2) return arr

      const N = arr.length - 1
      // 1.外层控制循环次数
      for (let i = 0; i < N; i++) {
        // 2.内层控制每个元素比较次数
        // 说明：N-i 外层循环一次表示已经排好一个元素 就不用再比较了
        for (let j = 0; j < N - i; j++) {
          // 自增 >
          // 自减 <
          if (arr[j] > arr[j + 1]) {
            const 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
    14
    15
    16
    17
    18
    function bubbleSort(arr) {
      if (!arr || arr.length < 2) return arr

      const N = arr.length - 1
      for (let i = N; i > 0; i--) {
        for (let j = N; j > N - i; j--) {
          // 自增 <
          // 自减 >
          if (arr[j] < arr[j - 1]) {
            const 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
    14
    15
    16
    17
    18
    19
    20
    function bubbleSort(arr) {
      if (!arr || arr.length < 2) return arr

      let N = arr.length - 1
      while (N > 1) {
        let lastChange = 1
        for (let j = 0; j < N; j++) {
          // 自增 >
          // 自减 <
          if (arr[j] > arr[j + 1]) {
            arr[j] = arr[j] + arr[j + 1]
            arr[j + 1] = arr[j] - arr[j + 1]
            arr[j] = arr[j] - arr[j + 1]
            lastChange = j
          }
        }
        N = lastChange
      }
      return arr
    }

3. 插入排序

核心思想：将数据按照一定的顺序一个一个的插入到有序的表中，最终得到序列就是已经排好的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const insertionSort = (arr) => {
  if (!arr || arr.length < 2) return arr

  // 1.外层控制循环次数
  for (let i = 1; i < arr.length; i++) {
    const temp = arr[i]
    let j = i
    // 2. 循环条件符合后j的位置的前面都已经排好序了
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1]
      j--
    }
    arr[j] = temp
  }
  return arr
}

4. 快速排序

核心思想：从数组中选择一个元素作为基准，将数组中小于基准的元素放到基准的左边，大于基准的元素放到基准的右边，然后再对左右两边的数组重复上述操作，直到数组完全排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const quickSort = function (arr) {
  if (!arr || arr.length < 2) return arr

  const left = []
  const right = []
  const mid = arr.splice((arr.length / 2 >> 0), 1)[0]

  for (let i = 0; i < arr.length; i++) {
    const item = arr[i]
    item <= mid ? left.push(item) : right.push(item)
  }
  return [...quickSort(left), mid, ...quickSort(right)]
}

console.log(quickSort([2, 1, 3, 6, 8]))

5. 归并排序

核心思想：将数组分成两部分，分别进行排序，然后将排序好的两部分合并在一起，最终得到的结果就是排序好的数组。

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
const process = (left, right) => {
  const result = []
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  while (left.length) {
    result.push(left.shift())
  }
  while (right.length) {
    result.push(right.shift())
  }
  return result
}

const mergeSort = (arr) => {
  if (!arr || arr.length < 2) return arr

  const midIndex = arr.length >> 1
  const left = arr.slice(0, midIndex)
  const right = arr.slice(midIndex)
  return merge(mergeSort(left), mergeSort(right))
}

6. 希尔排序

核心思想：将数组按照一定的间隔分成几个子数组，然后对子数组进行插入排序，然后缩小间隔，重复上述操作，直到间隔为1，最后对整个数组进行插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const shell = (arr) => {
  if (!arr || arr.length < 2) {
    return arr
  }

  let gap = Math.floor(arr.length / 2)
  while (gap > 0) {
    for (let i = gap; i < arr.length; i++) {
      const temp = arr[i]
      let j = i
      while (j > 0 && arr[j - gap] > temp) {
        arr[j] = arr[j - gap]
        j -= gap
      }
      arr[j] = temp
    }
    gap = Math.floor(gap / 2)
  }
  return arr
}

7. 堆排序

核心思想：将数组构建成一个大根堆，然后将堆顶元素与最后一个元素交换，然后将剩余的元素继续构建成一个大根堆，重复上述操作，直到数组完全排序。

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
42
43
44
45
46
47
48
49
50
const heapSort = (arr) => {
  if (!arr || arr.length < 2) return

  for (let i = 0; i < arr.length; i++) {
    // 第一步✅
    heapInsert(arr, i)
  }

  let heapSize = arr.length

  // 第二步与第三步✅
  while (heapSize > 0) {
    // 交换第一位与最后一位 并且heapSize减1
    swap(arr, 0, --heapSize)

    // 进行heapify 使之保持大根堆 向下调整的过程
    heapify(arr, 0, heapSize)
  }
}

function swap(arr, i, j) {
  const tmp = arr[i]
  arr[i] = arr[j]
  arr[j] = tmp
}

// 向上调整的过程
function heapInsert(arr, index) {
  // > 大顶推
  // < 小顶推
  while (arr[index] > arr[Math.floor((index - 1) / 2)]) {
    swap(arr, index, Math.floor((index - 1) / 2))
    index = Math.floor((index - 1) / 2)
  }
}

function heapify(arr, index, heapSize) {
  let left = 2 * index + 1

  while (left < heapSize) {
    let largest =
      left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left
    largest = arr[index] > arr[largest] ? index : largest

    if (largest === index) break
    swap(arr, index, largest)
    index = largest
    left = 2 * index + 1
  }
}

8. 计数排序

核心思想：将数组中的元素作为数组的下标，统计每个元素出现的次数，然后将统计好的数组按照下标顺序依次输出，最终得到的结果就是排序好的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const countingSort = (arr) => {
  if (!arr || arr.length < 2) return arr

  const maxValue = Math.max(...arr)
  const 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
}

9. 桶排序

核心思想：将数组中的元素分到不同的桶中，对每个桶中的元素进行排序，然后再将桶中的元素依次取出，即可得到一个有序的数组。

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
const bucketSort = (arr, bucketSize) => {
  if (!arr || arr.length < 2) return arr

  const len = arr.length
  const min = Math.min(...arr)
  const max = Math.max(...arr)
  const bucketCount = Math.floor((max - min) / bucketSize) + 1
  const buckets = new Array(bucketCount)
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = []
  }

  for (let i = 0; i < len; i++) {
    const index = Math.floor((arr[i] - min) / bucketSize)
    buckets[index].push(arr[i])
  }

  arr.length = 0
  for (let i = 0; i < bucketCount; i++) {
    insertion(buckets[i])
    for (let j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j])
    }
  }
  return arr
}

10. 基数排序

核心思想：将整数按位数切割成不同的数字，然后按每个位数分别比较。

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
const radixSort = (arr, maxDigit) => {
  if (!arr || arr.length < 2) return arr

  const mod = 10
  const dev = 1
  for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    const counter = []
    for (let j = 0; j < arr.length; j++) {
      const bucket = parseInt((arr[j] % mod) / dev)
      if (!counter[bucket]) {
        counter[bucket] = []
      }
      counter[bucket].push(arr[j])
    }
    let pos = 0
    for (let j = 0; j < counter.length; j++) {
      let value = null
      if (counter[j]) {
        while ((value = counter[j].shift()) !== undefined) {
          arr[pos++] = value
        }
      }
    }
  }
  return arr
}

11. 二分查找

核心思想：在有序数组中，取中间值与目标值进行比较，如果中间值大于目标值，则在左侧继续查找，如果中间值小于目标值，则在右侧继续查找，如果相等则返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const binarySearch = (arr, target) => {
  if (!arr || arr.length < 1) return -1

  let low = 0
  let high = arr.length - 1
  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] > target) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return -1
}