Sort
1 bubble
最好时间复杂度 O(n),最坏时间复杂度 O(n^2),平均时间复杂度也是 O(n^2)
不需要额外的空间，空间复杂度是 O(1)。排序过程中，当元素相同时不交换，稳定排序算法
原理：冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作
//best version
//两两对比，每次移动一个最大的item到最后
const bubble = (arr) => {
if (!arr || !Array.isArray(arr)) return
const len = arr.length
if (len < 2) return arr
for (let i = 0; i < len; i++) {
let isSwap = false
//每轮后面换好的不需要再进行比较
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
isSwap = true
}
}
//若当前轮无冒泡说明已排完，直接跳出
if (!isSwap) break
}
return arr
}2 insert
最好时间复杂度 O(n),最坏时间复杂度 O(n^2),平均时间复杂度也是 O(n^2)
不需要额外的空间，空间复杂度是 O(1)。排序过程中，当元素相同时不交换，稳定排序算法
原理：将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间元素为空
const insert = (arr) => {
if (!arr || !Array.isArray(arr)) return
const len = arr.length
if (len < 2) return arr
//遍历无序区，一开始第一个数是有序区
for (let i = 1; i < len; i++) {
const cur = arr[i]
//依次跟前面有序区进行比较
let j = i - 1
while (j >= 0 && arr[j] > cur) {
//有序区依次往后挪,有序区是一直有序的,不断寻找无序区里的当前cur应该放在有序区的位置
arr[j + 1] = arr[j]
j--
}
//cur放在该放的有序区位置上
arr[j + 1] = cur
}
return arr
}3 select
最好时间复杂度 O(n),最坏时间复杂度 O(n^2),平均时间复杂度也是 O(n^2)
不需要额外的空间，空间复杂度是 O(1)。排序过程中，==不稳定==排序算法
原理：先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。依次类推，直到所有元素均排序完毕
const select = (arr) => {
if (!arr || !Array.isArray(arr)) return
const len = arr.length
if (len < 2) return arr
//双循环不重复
//有序区
for (let i = 0; i < len - 1; i++) {
//存放当前循环中最小index,默认循环初始值
//有序区的末尾坐标,此处应放下面找到的无序区的最小值
let lastMinIdx = i
//无序区找最小值
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[lastMinIdx]) lastMinIdx = j
}
//将最小值放到有序序列的最后(去掉这一行不稳定)
if (lastMinIdx !== i) {
;[arr[i], arr[lastMinIdx]] = [arr[lastMinIdx], arr[i]]
}
}
return arr
}4 quick
最好 O(nlogn)、最坏 O(n^2)、平均时间复杂度都是 O(nlogn)
空间复杂度为 O(n), ==不稳定==的排序算法
原理：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到两边的中间。经过这一步操作之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 pivot-1 之间都是小于 pivot 的，后面是 pivot，后面的 pivot+1 到 r 之间是大于 pivot 的，根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，所有的数据都有序了
// 大雪菜version 双指针
// 1 确定分界点 可以arr[l]、arr[r]、arr[(l + r) / 2]
// 2 调整该区间
// 3 递归处理左右子区间
const quick = (arr) => {
if (!arr || !Array.isArray(arr)) return
const len = arr.length
if (len < 2) return arr
const helper = (arr, l, r) => {
if (l >= r) return
//x = arr[r] or arr[(l + r) / 2]
//使得 nums[l..p-1] <= nums[p] < nums[p+1..r]
const pivot = arr[l]
let i = l - 1,
j = r + 1
while (i < j) {
//上面外扩，这里直接先移动
while (arr[++i] < pivot);
while (arr[--j] > pivot);
if (i < j) [arr[i], arr[j]] = [arr[j], arr[i]]
}
//两边对称的
//helper(arr, l, i - 1)
//helper(arr, i, r)
helper(arr, l, j)
helper(arr, j + 1, r)
return arr
}
return helper(arr, 0, len - 1)
}
const quick = (arr) => {
if (!arr || !Array.isArray(arr)) return
const len = arr.length
if (len < 2) return arr
const partition = (arr, l, r) => {
//设最右边为pivot
const pivot = r
let index = l
for (let i = index; i < r; i++) {
if (arr[i] < arr[pivot]) {
//大的放pivot后,小的放pivot前,不稳定
;[arr[i], arr[index]] = [arr[index], arr[i]]
//记录有多少个比pivot小的
index++
}
}
//pivot放左右已排好序列中间
;[arr[index], arr[pivot]] = [arr[pivot], arr[index]]
return index
}
const helper = (arr, l, r) => {
if (l >= r) return
//取得pivot坐标
const pos = partition(arr, l, r)
helper(arr, l, pos - 1)
helper(arr, pos + 1, r)
//返回排序好的当前区
return arr
}
return helper(arr, 0, arr.length - 1)
}
//快选
const quickChoose = (arr, n, k) => {
const helper = (arr, l, r, k) => {
if (l === r) return arr[l]
const x = arr[l]
let i = l - 1,
j = r + 1
while (i < j) {
while (arr[++i] < x);
while (arr[--j] > x);
if (i < j) [arr[i], arr[j]] = [arr[j], arr[i]]
}
//排完后看左边的数字个数
const sl = j - l + 1
if (k <= sl) return helper(arr, l, j, k)
return helper(arr, j + 1, r, k - sl)
}
return helper(arr, 0, n - 1, k)
}5 merge
最好、最坏、平均时间复杂度都是 O(nlogn)
空间复杂度方面，由于每次合并的操作都需要开辟基于数组的临时内存空间，空间复杂度为 O(n),稳定排序算法
原理：先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。归并排序使用的就是分治思想
// 大雪菜version
// 1 确定分界点 mid = (l + r) / 2
// 2 递归排序left, right
// 3 归并 - 合二为一
const merge = (arr) => {
if (!arr || !Array.isArray(arr)) return
const len = arr.length
if (len < 2) return arr
const helper = (arr, l, r, tmp) => {
if (l >= r) return
const mid = (l + r) >> 1
//先递
helper(arr, l, mid, tmp)
helper(arr, mid + 1, r, tmp)
//再归两段数组
let k = 0,
i = l,
//当前层后部分数组的开始坐标
j = mid + 1
while (i <= mid && j <= r) tmp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++]
while (i <= mid) tmp[k++] = arr[i++]
while (j <= r) tmp[k++] = arr[j++]
//复制回当前层arr
for (let i = l, j = 0; i <= r; i++, j++) arr[i] = tmp[j]
return arr
}
return helper(arr, 0, len - 1, [])
}6 heap
最好 O(nlogn)、最坏 O(nlogn)、平均时间复杂度都是 O(nlogn)
空间复杂度为 O(1), 稳定的排序算法
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足 R[1,2…n-1]<=R[n]；
由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成
const heap = (arr) => {
if (!arr || !Array.isArray(arr)) return
let len = arr.length
if (len < 2) return arr
//堆化,查找三个点中的最大点
const down = (arr, i) => {
const lSon = 2 * i + 1,
rSon = 2 * i + 2
let largest = i
if (lSon < len && arr[lSon] > arr[largest]) largest = lSon
if (rSon < len && arr[rSon] > arr[largest]) largest = rSon
if (largest != i) {
;[arr[largest], arr[i]] = [arr[i], arr[largest]]
//交换后继续看交换后的那个节点的子树三个节点是否满足条件
down(arr, largest)
}
}
const buildMaxHeap = (arr) => {
//从第一个非叶子节点开始创建
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) down(arr, i)
}
buildMaxHeap(arr)
//每次堆顶和最后一个元素交换，再堆化，即无序区减1，有序区加1
for (let i = len - 1; i >= 1; i--) {
;[arr[i], arr[0]] = [arr[0], arr[i]]
len--
//交换后从顶点开始down
down(arr, 0)
}
return arr
}如何手写一个小根堆（完全二叉树,坐标从 1 开始）
插入一个元素 heap[++size] = x; up(size)
求集合当中的最小值 heap[1]
删除最小值 heap[1] = heap[size]; size--; down(1)
删除任意一个元素 heap[k] = heap[size]; size--; down(k); up(k)
修改任意一个元素 heap[k] = x; size--; down(k); up(k)
Last updated