3个O(nlogn)排序

一、快速排序

快速排序——每次选取一个基准值,将数组分为小于基准值和大于基准值的两部分,再重复之前的递归操作

  • 不稳定
  • O(nlogn)

1. 单路快排

对于含有大量重复元素的情况，性能会显著降低，甚至退化成O(n²)

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
function quickSort (arr) {
  _quickSort(arr, 0, arr.length - 1)

  // 对arr[l...r]进行排序
  function _quickSort (arr, l, r) {
    if (l >= r) {
      return
    }
    const p = _partition(arr, l, r)
    _quickSort(arr, l, p - 1)
    _quickSort(arr, p + 1, r)
  }

  function _partition (arr, l, r) {
    // arr[l+1...j] < p
    // arr[j+1...i-1] >= p
    // 随机选取标定值p
    const randomIndex = ~~(Math.random() * (r - l + 1) + l)
    swap(arr, l, randomIndex)
    let p = arr[l]
    let j = l
    for (let i = l + 1; i <= r; i++) {
      if (arr[i] < p) {
        j++
        swap(arr, i, j)
      }
    }
    swap(arr, l, j)
    return j
  }
}

2. 双路快排

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 quickSort2 (arr) {
  _quickSort(arr, 0, arr.length - 1)

  // 对arr[l...r]进行排序
  function _quickSort (arr, l, r) {
    if (l >= r) {
      return
    }
    const p = _partition(arr, l, r)
    _quickSort(arr, l, p - 1)
    _quickSort(arr, p + 1, r)
  }

  function _partition (arr, l, r) {
    // arr[l+1...i-1] <= p
    // arr[j+1...r] >= p
    const randomIndex = ~~(Math.random() * (r - l + 1) + l)
    swap(arr, l, randomIndex)
    let p = arr[l]
    let i = l + 1, j = r
    while (true) {
      while (i <= j && arr[i] < p) i++
      while (i <= j && arr[j] > p) j--
      if (i >= j) break
      swap(arr, i, j)
      i++
      j--
    }
    swap(arr, l, j)
    return j
  }
}

3. 三路快排

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
function quickSort3 (arr) {
  _quickSort(arr, 0, arr.length - 1)

  // 对arr[l...r]进行排序
  function _quickSort (arr, l, r) {
    if (l >= r) {
      return
    }
    const [lt, gt] = _partition(arr, l, r)
    _quickSort(arr, l, lt - 1)
    _quickSort(arr, gt, r)
  }

  function _partition (arr, l, r) {
    // arr[l+1...lt] < p
    // arr[lt+1...gt-1] = p
    // arr[gt...r] > p
    const randomIndex = ~~(Math.random() * (r - l + 1) + l)
    swap(arr, l, randomIndex)
    const p = arr[l]
    let lt = l, i = l + 1, gt = r + 1
    while (i < gt) {
      if (arr[i] < p) {
        lt++
        swap(arr, i, lt)
        i++
      } else if (arr[i] > p) {
        gt--
        swap(arr, i, gt)
      } else { // arr[i] == p
        i++
      }
    }
    swap(arr, lt, l)
    // arr[l+1...lt-1] < p
    // arr[lt...gt-1] = p
    // arr[gt...r] > p
    return [lt, gt]
  }
}

二、归并排序

归并排序：将原数组对半分割成子数组,然后递归分割子数组，直至不能分割，然后分别排序子数组,再依次合并

  • 稳定
  • O(nlogn)
  • 无法原地排序，需要额外的O(n)空间

1. 自顶向下

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
function mergeSort (arr) {
  _mergeSort(arr, 0, arr.length - 1)

  // 递归调用归并排序，对arr[l...r]的范围进行排序
  function _mergeSort (arr, l, r) {
    if (l >= r) {
      return
    }

    const mid = l + ((r - l) >> 1)
    _mergeSort(arr, l, mid)
    _mergeSort(arr, mid + 1, r)
    _merge(arr, l, mid, r)
  }

  // 将arr[l...mid]和arr[mid+1...r]两部分合并
  function _merge (arr, l, mid, r) {
    const temp = []
    for (let i = l; i <= r; i++) {
      temp[i] = arr[i]
    }

    let i = l, j = mid + 1
    for (let k = l; k <= r; k++) {
      if (i > mid) { // i越界
        arr[k] = temp[j]
        j++
      } else if (j > r) { // j越界
        arr[k] = temp[i]
        i++
      } else if (temp[i] <= temp[j]) { // temp[i] <= temp[j]
        arr[k] = temp[i]
        i++
      } else { // temp[i] > temp[j]
        arr[k] = temp[j]
        j++
      }
    }
  }
}

优化

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
51
52
53
54
55
56
57
function mergeSort (arr) {
  // 优化3：减少数组申请空间开销
  const tempArr = new Array(arr.length)
  _mergeSort(arr, 0, arr.length - 1)

  // 递归调用归并排序，对arr[l...r]的范围进行排序
  function _mergeSort (arr, l, r) {
    // 优化1：当数据量小时,转而使用插入排序会更快
    if (r - l <= 15) {
      insertSort(arr, l, r)
      return
    }

    const mid = l + ((r - l) >> 1)
    _mergeSort(arr, l, mid)
    _mergeSort(arr, mid + 1, r)
    // 优化2：如果已经有序,则不合并,否则,合并
    if (arr[mid] > arr[mid + 1])
      _merge(arr, l, mid, r)
  }

  // 将arr[l...mid]和arr[mid+1...r]两部分合并
  function _merge (arr, l, mid, r) {
    // 优化3：减少数组申请空间开销
    for (let i = l; i <= r; i++) {
      tempArr[i] = arr[i]
    }

    let i = l, j = mid + 1
    for (let k = l; k <= r; k++) {
      if (i > mid) { // i越界
        arr[k] = tempArr[j]
        j++
      } else if (j > r) { // j越界
        arr[k] = tempArr[i]
        i++
      } else if (tempArr[i] <= tempArr[j]) { // tempArr[i] <= tempArr[j]
        arr[k] = tempArr[i]
        i++
      } else { // tempArr[i] > tempArr[j]
        arr[k] = tempArr[j]
        j++
      }
    }
  }

  function insertSort (arr, l, r) {
    for (let i = l + 1; i <= r; i++) {
      const temp = arr[i]
      let j
      for (j = i; j - 1 >= l && temp < arr[j - 1]; j--) {
        arr[j] = arr[j - 1]
      }
      arr[j] = temp
    }
  }
}

2. 自底向上

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
function mergeSortNR (arr) {
  const tempArr = new Array(arr.length)

  // 遍历合并区间的长度
  for (let size = 1; size < arr.length; size = size * 2) {
    // 合并[i ... i+size-1] 和 [i+size ... Math.min(i + 2 * size - 1, arr.length - 1)]
    for (let i = 0; i + size < arr.length; i = i + 2 * size) { // i+size保证右边的区间存在
      const l = i,
        mid = i + size - 1,
        r = Math.min(i + 2 * size - 1, arr.length - 1)
      if (arr[mid] > arr[mid + 1]) {
        _merge(arr, l, mid, r)
      }
    }
  }

  function _merge (arr, l, mid, r) {
    for (let i = l; i <= r; i++) {
      tempArr[i] = arr[i]
    }

    let i = l, j = mid + 1
    for (let k = l; k <= r; k++) {
      if (i > mid) { // i越界
        arr[k] = tempArr[j]
        j++
      } else if (j > r) { // j越界
        arr[k] = tempArr[i]
        i++
      } else if (tempArr[i] <= tempArr[j]) { // tempArr[i] <= tempArr[j]
        arr[k] = tempArr[i]
        i++
      } else { // tempArr[i] > tempArr[j]
        arr[k] = tempArr[j]
        j++
      }
    }
  }
}

优化

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
51
52
53
54
55
56
57
58
function mergeSortNR (arr) {
  const tempArr = new Array(arr.length)

  // 优化1
  for (let i = 0; i < arr.length; i = i + 16) {
    const l = i,
      r = Math.min(i + 15, arr.length - 1)
    insertSort(arr, l, r)
  }

  // 遍历合并区间的长度
  for (let size = 16; size < arr.length; size = size * 2) {
    // 合并[i ... i+size-1] 和 [i+size ... Math.min(i + 2 * size - 1, arr.length - 1)]
    for (let i = 0; i + size < arr.length; i = i + 2 * size) { // i+size保证右边的区间存在
      const l = i,
        mid = i + size - 1,
        r = Math.min(i + 2 * size - 1, arr.length - 1)
      // 优化2
      if (arr[mid] > arr[mid + 1]) {
        _merge(arr, l, mid, r)
      }
    }
  }

  function _merge (arr, l, mid, r) {
    for (let i = l; i <= r; i++) {
      tempArr[i] = arr[i]
    }

    let i = l, j = mid + 1
    for (let k = l; k <= r; k++) {
      if (i > mid) { // i越界
        arr[k] = tempArr[j]
        j++
      } else if (j > r) { // j越界
        arr[k] = tempArr[i]
        i++
      } else if (tempArr[i] <= tempArr[j]) { // tempArr[i] <= tempArr[j]
        arr[k] = tempArr[i]
        i++
      } else { // tempArr[i] > tempArr[j]
        arr[k] = tempArr[j]
        j++
      }
    }
  }

  function insertSort (arr, l, r) {
    for (let i = l + 1; i <= r; i++) {
      const temp = arr[i]
      let j
      for (j = i; j - 1 >= l && temp < arr[j - 1]; j--) {
        arr[j] = arr[j - 1]
      }
      arr[j] = temp
    }
  }
}

三、堆排序

堆排序：将数组调整成大根堆/小根堆,每次将第一个元素与最后一个未排好序的元素交换

  • 不稳定
  • O(nlogn)
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
function heapSort (arr) {
  const lastParentIndex = ~~((arr.length - 1) / 2)
  for (let i = lastParentIndex; i >= 0; i--) {
    _siftDown(arr, i, arr.length)
  }

  for (let i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i)
    _siftDown(arr, 0, i)
  }
  return arr

  function _siftDown(arr, i, n) {
    while (2 * i + 1 < n) {
      let j = 2 * i + 1
      if (j + 1 < n && arr[j + 1] > arr[j]) {
        j = j + 1
      }
      if (arr[i] > arr[j]) {
        break
      }
      swap(arr, i, j)
      i = j
    }
  }
}

helper.js

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * 交换数组中的两个值
 */

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

  // 只有当 i !== j 时才可以
  // arr[i] ^= arr[j]
  // arr[j] ^= arr[i]
  // arr[i] ^= arr[j]
}

/**
 * 生成一个长度为n的有序数组，[0...n)
 */

function generateOrderedArray (n) {
  const arr = new Array(n)
  for (let i = 0; i < n; i++)
    arr[i] = i
  return arr
}

/**
 * 生成一个长度为n的随机数组，每个值的范围在[0,bound)
 */

function generateRandomArray (n, bound) {
  const arr = new Array(n)
  for (let i = 0; i < n; i++)
    arr[i] = ~~(Math.random() * bound)
  return arr
}

/**
 * 生成一个长度为n的随机数组，每个值的范围在[start,end]
 */

function generateRandomArrayByStartAndEnd (n, start, end) {
  const arr = new Array(n)
  for (let i = 0; i < n; i++)
    arr[i] = ~~(Math.random() * (end - start + 1) + start)
  return arr
}

/**
 * 判断一个数组是否有序
 */

function isSorted (arr) {
  for (let i = 1; i < arr.length; i++)
    if (arr[i - 1] > arr[i])
      return false
  return true
}

/**
 * 测试排序算法性能
 */

function testSort (fn, arr) {
  const startTime = Date.now()
  fn(arr)
  const endTime = Date.now()
  const spendTime = endTime - startTime
  if (!isSorted(arr)) {
    console.log(`${fn.name} failed!`)
    const debugArr = generateRandomArray(5, 10)
    console.log(`Before sort: [${debugArr.join(', ')}]`)
    fn(debugArr)
    console.log(`After sort: [${debugArr.join(', ')}]`)
    return
  }

  console.log(`${fn.name}: ${arr.length}, time: ${spendTime / 1000}s`)
}


module.exports = {
  swap,
  generateOrderedArray,
  generateRandomArray,
  generateRandomArrayByStartAndEnd,
  isSorted,
  testSort
}