排序算法
冒泡
O(n2) O(1)
相邻元素进行比较，如果前一个元素值大于后一个元素值，则交换，这样一轮下来，将最大的数在最右边冒泡出来。
简单说：把大的往后排
ts
function bubbleSort(arr: number[]): number[] {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
console.log(`第${i + 1}轮`, arr)
}
return arr
}
console.log('🌰', bubbleSort([3, 9, 1, 4, 2]))选择
O(n2) O(1)
找到数组中最小的值，选中它并放到第一位，接着找到数组中第二小的值，选中它并放到第二位。
简单说：把小的往前排
ts
function selectionSort(arr: number[]): number[] {
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i
for (let j = i; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
if (minIndex !== i) {
;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
console.log(`第${i + 1}轮`, arr)
}
return arr
}
console.log('🌰', selectionSort([3, 9, 1, 4, 2]))插入
O(n2) O(1)
每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着，它和第二项进行比较——第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较（它是该插入到第一、第二还是第三的位置呢），以此类推。
简单说：也是把小的往前排
ts
function insertionSort(arr: number[]): number[] {
let n = arr.length
let preIndex: number, current: number
for (let i = 1; i < n; i++) {
preIndex = i - 1
current = arr[i]
//如果不比current小就停止了，prevIndex不会再一直递减到0
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex]
preIndex--
}
arr[preIndex + 1] = current
console.log(`第${i}轮`, arr)
}
return arr
}
console.log('🌰', insertionSort([3, 9, 1, 4, 2]))归并
分治 递归 双指针 O(nlogn) O(n)
是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。
ts
function mergeSort(arr: number[]): number[] {
const rec = (arr: number[]): number[] => {
//分解
const len = arr.length
if (len === 1) {
return arr
}
const mid = Math.floor(len / 2)
const leftArr = arr.slice(0, mid)
const rightArr = arr.slice(mid)
console.log('分解', 'left:', leftArr, 'right:', rightArr)
const orderLeftArr = rec(leftArr)
const orderRightArr = rec(rightArr)
//合并，双指针
const res = []
let li = 0 //left index
let ri = 0 //right index
while (li < orderLeftArr.length || ri < orderRightArr.length) {
const lv = orderLeftArr[li] //left number
const rv = orderRightArr[ri] //right number
if ((lv && rv && lv < rv) || (lv && !rv)) {
res.push(lv)
li++
} else if ((lv && rv && lv > rv) || (!lv && rv)) {
res.push(rv)
ri++
} else {
res.push(lv)
res.push(rv)
li++
ri++
}
}
console.log('🈴️ 合并', res)
return res
}
return rec(arr)
}
console.log('🌰', mergeSort([3, 9, 1, 2, 4, 70, 34, 56]))快速
分治 递归 O(nlogn) O(nlogn)
从数组中任意选择一个基准，所有比基准小的元素放在基准前面，比基准大的元素放在基准后面，递归的对基准前后的子数组再进行划分。
ts
function quickSort(array: number[]): number[] {
const rec = (arr: number[]) => {
const len = arr.length
//!!!leftArr或rightArr可能为空
if (len <= 1) {
return arr
}
const mid = arr[0]
const leftArr = []
const rightArr = []
for (let i = 1; i < len; i++) {
const val = arr[i]
if (val < mid) {
leftArr.push(val)
} else {
rightArr.push(val)
}
}
console.log(`基准: ${mid} 分解`, 'left:', leftArr, 'right:', rightArr)
const res = [...rec(leftArr), mid, ...rec(rightArr)]
console.log(`基准: ${mid} 合并`, res)
return res
}
return rec(array)
}
console.log('🌰', quickSort([3, 9, 1, 2, 4, 70, 34, 56]))堆
最大堆可以得到一个升序的数组，最小堆可以得到一个降序的数组
用最大堆排序步骤：
- 用数组创建一个最大堆
- 将
堆顶与堆尾（堆最后一个值）交换，将堆.legnth -1 - 将剩下的元素不断重复 前 2 步，直到堆大小为 1
ts
function heapSort(nums: number[]): number[] {
let heapSize = nums.length
const len = nums.length
buildMaxHeap(heapSize)
console.log('init maxHeap', [...nums])
while (heapSize > 1) {
swap(nums, 0, --heapSize)
maxHeapify(0, heapSize)
console.log('', heapSize, [...nums])
}
return nums
// 自下而上构建一颗大顶堆
function buildMaxHeap(heapSize: number): void {
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
maxHeapify(i, heapSize)
}
}
// 从左向右，自上而下的调整节点
function maxHeapify(i: number, heapSize: number): void {
let l = i * 2 + 1
let r = i * 2 + 2
let largest = i
if (l < heapSize && nums[l] > nums[largest]) {
largest = l
}
if (r < heapSize && nums[r] > nums[largest]) {
largest = r
}
if (largest !== i) {
swap(nums, i, largest)
maxHeapify(largest, heapSize)
}
}
//交换
function swap(arr: number[], i: number, j: number) {
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
console.log('🌰', heapSort([0, 1, 2, 2, 3, 7, 6, 1]))