堆排序(HeapSort)

方式

1. 构建结尾下标，上浮下沉函数
2. 依次对每个下标进行上浮
3. 把结尾元素与首元素进行交换，并重置结尾下标，对首元素进行下沉，重复直到结尾下标为 0

核心代码

import { Comparator } from '@/shared';

export const heapSort = <T = any>(compare: Comparator<T>, list: T[]) => {
    let lastIndex = list.length - 1;
    const shiftUp = (index: number): void => {
        if (index === 0) return;
        const parentIndex = (index - 1) >> 1;
        if (compare(list[index], list[parentIndex]) > 0) {
            [list[index], list[parentIndex]] = [list[parentIndex], list[index]];
            shiftUp(parentIndex);
        }
    };
    const shiftDown = (index: number): void => {
        let childIndex = index * 2 + 1;
        if (childIndex > lastIndex) return;
        if (childIndex + 1 <= lastIndex && compare(list[childIndex + 1], list[childIndex]) > 0)
            childIndex++;
        if (compare(list[childIndex], list[index]) > 0) {
            [list[childIndex], list[index]] = [list[index], list[childIndex]];
            shiftDown(childIndex);
        }
    };
    for (let i = 0; i <= lastIndex; i++) shiftUp(i);
    while (lastIndex > 0) {
        [list[0], list[lastIndex--]] = [list[lastIndex], list[0]];
        shiftDown(0);
    }
};