AHABHGK

1// min: O(n), max: O(n^2)
2// O(1) 原地排序
3// 稳定
4function bubbleSort(arr) {
5  for (let i = 0; i < arr.length; i++) {
6    let hasSwap = false
7    for (let j = 0; j < arr.length - i - 1; j++) {
8      if (arr[j] > arr[j + 1]) {
9        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
10        hasSwap = true
11      }
12    }
13    if (!hasSwap) break
14  }
15  return arr
16}
17
18// min: O(n), max: O(n^2)
19// O(1) 原地排序
20// 稳定
21function insertSort(arr) {
22  for (let i = 1; i < arr.length; i++) {
23    let value = arr[i]
24    let j = i - 1
25    for (; j >= 0; j--) {
26      if (arr[j] > value) {
27        arr[j + 1] = arr[j]
28      } else break
29    }
30    arr[j + 1] = value
31  }
32  return arr
33}
34
35// min: O(n^2), max: O(n^2)
36// O(1)
37// 不稳定
38function selectSort(arr) {
39  for (let i = 0; i < arr.length - 1; i++) {
40    let index = i
41    for (let j = i + 1; j < arr.length; j++) {
42      if (arr[j] < arr[index]) {
43        index = j
44      }
45    }
46    [arr[index], arr[i]] = [arr[i], arr[index]]
47  }
48  return arr
49}
50
51// min: O(nlogn), max: O(nlogn)
52// O(n)
53// 稳定
54function mergeSort(arr) {
55  return slice(0, arr.length - 1)
56
57  function slice(left, right) {
58    if (left >= right) return
59    let mid = Math.floor((left + right) / 2)
60    slice(left, mid)
61    slice(mid + 1, right)
62    merge(left, mid, right)
63  }
64  function merge(left, mid, right) {
65    let tmp = []
66    let i = left, j = mid + 1
67    while (i <= mid && j <= right) {
68      tmp.push(arr[i] < arr[j] ? arr[i++] : arr[j++])
69    }
70    while (i <= mid) tmp.push(arr[i++])
71    while (j <= right) tmp.push(arr[j++])
72    for (let k = 0; k < tmp.length; k++) {
73      arr[left + k] = tmp[k]
74    }
75  }
76}
77
78// min: O(nlogn), max: O(n^2), ava: O(nlogn)
79// O(logn)
80// 不稳定
81function quickSort(arr) {
82  return sort(0, arr.length - 1)
83
84  function sort(begin, end) {
85    if (begin > end) return
86    let pivot = partition(begin, end)
87    sort(begin, pivot - 1)
88    sort(pivot + 1, end)
89  }
90  function partition(begin, end) {
91    let counter = begin, pivot = end
92    for (let i = begin; i < end; i++) {
93      if (arr[i] < arr[pivot]) {
94        ;[arr[counter], arr[i]] = [arr[i], arr[counter]]
95        counter++
96      }
97    }
98    ;[arr[counter], arr[pivot]] = [arr[pivot], arr[counter]]
99    return counter
100  }
101}
102
103// O(nlogn)
104// O(1)
105// not stable
106function heapSort(arr) {
107  if (arr.length === 0) return
108  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
109    heapify(arr, arr.length, i)
110  }
111  /**
112   * heapPush: O(logn)
113   *        8
114   *    5       6
115   *  1   3   0   2
116   */
117  for (let i = arr.length - 1; i > 0; i--) {
118    ;[arr[0], arr[i]] = [arr[i], arr[0]]
119    heapify(arr, i, 0)
120  }
121  /**
122   * heapPop: O(logn)
123   *        8        ->        2    |   ->        6    |
124   *    5       6    ->    5       6|   ->    5       2|
125   *  1   3   0   2  ->  1   3   0  |8  ->  1   3   0  |8
126   */
127  function heapify(arr, len, i) {
128    let left = 2 * i + 1, right = 2 * i + 2
129    let largest = i
130    if (left < len && arr[left] > arr[largest]) {
131      largest = left
132    }
133    if (right < len && arr[right] > arr[largest]) {
134      largest = right
135    }
136    if (largest !== i) {
137      ;[arr[largest], arr[i]] = [arr[i], arr[largest]]
138      heapify(arr, len, largest)
139    }
140  }
141}
142
143// max: O(nlogn) 一个桶, min: O(n) n 个桶
144// 可以处理大量数据的情况，分桶存入内存处理
145// 稳定性根据桶内的排序算法决定
146function bucketSort(arr, bucketSize) {
147  let max = Math.max(...arr)
148  let min = Math.min(...arr)
149  let bucketNum = Math.floor((max - min) / bucketSize) + 1
150  let buckets = Array.from({ length: bucketNum }, _ => [])
151  for (let i = 0; i < arr.length; i++) {
152    let index = Math.floor((arr[i] - min) / bucketSize)
153    buckets[index].push(arr[i])
154  }
155  let res = []
156  for (let i = 0; i < bucketNum; i++) {
157    res = res.concat(quickSort(buckets[i]))
158  }
159  return res
160}
161
162// 类似桶排序，保证 n 个桶
163// 负数和小数的情况下需要变为正数（+）和整数（*）
164function countSort(arr) {
165  let min = Math.min(...arr)
166  let max = Math.max(...arr)
167  let bucketNum = Math.floor((max - min) / 1) + 1
168  let buckets = Array.from({ length: bucketNum }, _ => 0)
169  for (let i = 0; i < arr.length; i++) {
170    buckets[arr[i] - min] += 1
171  }
172  let res = []
173  for (let i = 0; i < bucketNum; i++) {
174    for (let j = 0; j < buckets[i]; j++) {
175      res.push(i + min)
176    }
177  }
178  return res
179}
180
181// O(n)
182// 适合位数很大的情况，比如手机号排序
183function radixSort(arr) {
184  let digit = `${Math.max(...arr)}`.length
185  let start = 1
186  while (digit) {
187    start *= 10
188    let buckets = []
189    for(let i = 0; i < arr.length; i++) {
190      const index = arr[i] % start
191      !buckets[index] && (buckets[index] = [])
192      buckets[index].push(arr[i])
193    }
194    arr = []
195    for(let i = 0; i < buckets.length; i++) {
196      buckets[i] && (arr = arr.concat(buckets[i]))
197    }
198    digit -= 1
199  }
200  return arr
201}

1// 查找第一个值等于给定值的元素
2function binSearchFindFirst(arr, target) {
3  let left = 0
4  let right = arr.length - 1
5  while (left <= right) {
6    let mid = Math.floor((left + right) / 2)
7    if (target > arr[mid]) left = mid + 1
8    else if (target < arr[mid]) right = mid - 1
9    else {
10      if (mid === 0 || arr[mid - 1] !== target) return mid
11      else right = mid - 1
12    }
13  }
14  return -1
15}
16
17console.log(binSearchFindFirst([1, 3, 4, 5, 6, 8, 8, 8, 11, 18], 8))
18
19// 查找最后一个值等于给定值的元素
20function binSearchFindLatest(arr, target) {
21  let left = 0
22  let right = arr.length - 1
23  while (left <= right) {
24    let mid = Math.floor((left + right) / 2)
25    if (target > arr[mid]) left = mid + 1
26    else if (target < arr[mid]) right = mid - 1
27    else {
28      if (mid === arr.length - 1 || arr[mid + 1] !== target) return mid
29      else left = mid + 1
30    }
31  }
32  return -1
33}
34
35console.log(binSearchFindLatest([1, 3, 4, 5, 6, 8, 8, 8, 11, 18], 8))
36
37// 查找第一个大于等于给定值的元素
38function binSearchFindFirstGreaterEqual(arr, target) {
39  let left = 0
40  let right = arr.length - 1
41  while (left <= right) {
42    let mid = Math.floor((left + right) / 2)
43    if (arr[mid] >= target) {
44      if (mid === 0 || arr[mid - 1] < target) return mid
45      else right = mid - 1
46    } else left = mid + 1
47  }
48  return -1
49}
50
51console.log(binSearchFindFirstGreaterEqual([3, 4, 6, 7, 10], 5))
52
53// 查找最后一个小于等于给定值的元素
54function binSearchFindLatestLessEqual(arr, target) {
55  let left = 0
56  let right = arr.length - 1
57  while (left <= right) {
58    let mid = Math.floor((left + right) / 2)
59    if (arr[mid] <= target) {
60      if (mid === arr.length - 1 || arr[mid + 1] > target) return mid
61      else left = mid + 1
62    } else right = mid - 1
63  }
64  return -1
65}
66
67console.log(binSearchFindLatestLessEqual([3, 4, 6, 8, 9, 10], 7))

1// i 到 n 进行堆化
2function heapify(arr, n, i) {
3  while (true) {
4    let maxPos = i
5    if (i * 2 <= n && arr[i] < arr[i * 2]) maxPos = i * 2
6    if (i * 2 + 1 <= n && arr[maxPos] < arr[i * 2 + 1]) maxPos = i * 2 + 1
7    if (maxPos === i) break
8    ;[arr[i], arr[maxPos]] = [arr[maxPos], arr[i]]
9    i = maxPos
10  }
11}
12
13function heapSort(arr) {
14  function buildHeap(arr) {
15    for (let i = Math.floor(arr.length / 2); i > 0; i--) {
16      heapify(arr, arr.length, i)
17    }
18  }
19  buildHeap(arr)
20  let k = arr.length - 1
21  while (k > 1) {
22    ;[arr[1], arr[k]] = [arr[k], arr[1]]
23    k -= 1
24    heapify(arr, k, 1)
25  }
26  return arr
27}
28
29// arr[0] 没用，只是从 1 开始方便计算
30console.log(heapSort([0, 1, 3, 2, 5, 4, 2, 1, 0]))