排序算法

快速排序

核心思想

首先检查数组长度，如果数组长度小于等于1，那么直接返回，不需要排序。否则，选择数组中间的一个元素作为基准值，遍历数组，将小于基准值的元素放在左边，大于基准值的元素放在右边，然后递归地对左右两边的数组进行排序。

// npm run code src/code/algorithm/quick-sort.ts

export {};

function quickSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[0];
    const left: number[] = [];
    const right: number[] = [];

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}

// 示例
const array = [3, 6, 8, 10, 1, 2, 1];
console.log("Original array:", array);
const sortedArray = quickSort(array);
console.log("Sorted array:", sortedArray);

归并排序

核心思想

首先检查数组长度，如果数组长度小于等于1，那么直接返回，不需要排序。否则，将数组分成两半，并递归地调用自身来排序这两部分，然后将两个有序的数组合并成一个有序的数组。

// npm run code src/code/algorithm/merge-sort.ts

export { };

function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left: number[], right: number[]): number[] {
    let result: number[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 示例
const array = [3, 6, 8, 10, 1, 2, 1];
console.log("Original array:", array);
const sortedArray = mergeSort(array);
console.log("Sorted array:", sortedArray);

堆排序

核心思想

// npm run code src/code/algorithm/heapsort.ts

export { };

class MaxHeap {
    private heap: number[];

    constructor() {
        this.heap = [];
    }

    private getParentIndex(i: number): number {
        return Math.floor((i - 1) / 2);
    }

    private getLeftChildIndex(i: number): number {
        return 2 * i + 1;
    }

    private getRightChildIndex(i: number): number {
        return 2 * i + 2;
    }

    private swap(i: number, j: number) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

    public insert(key: number) {
        this.heap.push(key);
        let index = this.heap.length - 1;
        while (index !== 0 && this.heap[this.getParentIndex(index)] < this.heap[index]) {
            this.swap(this.getParentIndex(index), index);
            index = this.getParentIndex(index);
        }
    }

    public extractMax(): number | null {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop()!;

        const max = this.heap[0];
        this.heap[0] = this.heap.pop()!;
        this.heapify(0);

        return max;
    }

    private heapify(i: number) {
        const left = this.getLeftChildIndex(i);
        const right = this.getRightChildIndex(i);
        let largest = i;

        if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
            largest = left;
        }

        if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
            largest = right;
        }

        if (largest !== i) {
            this.swap(i, largest);
            this.heapify(largest);
        }
    }
}

function heapSort(arr: number[]): number[] {
    let heap = new MaxHeap();
    for (let num of arr) {
        heap.insert(num);
    }

    for (let i = arr.length - 1; i >= 0; i--) {
        arr[i] = heap.extractMax()!;
    }

    return arr;
}

// 示例
const array = [3, 6, 8, 10, 1, 2, 1];
console.log("Original array:", array);
const sortedArray = heapSort(array);
console.log("Sorted array:", sortedArray);

冒泡排序

核心思想

遍历数组，比较相邻的两个元素，如果前一个元素大于后一个元素，那么交换这两个元素的位置，然后继续遍历，直到没有元素需要交换。

// npm run code src/code/algorithm/bubble-sort.ts

export { };

function bubbleSort(arr: number[]): number[] {
    let n = arr.length;
    let swapped: boolean;

    do {
        swapped = false;
        for (let i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]]; // 交换元素
                swapped = true;
            }
        }
        n--;
    } while (swapped);

    return arr;
}

// 示例
const array = [3, 6, 8, 10, 1, 2, 1];
console.log("Original array:", array);
const sortedArray = bubbleSort(array);
console.log("Sorted array:", sortedArray);

选择排序

核心思想

首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

// npm run code src/code/algorithm/selection-sort.ts

export { };

function selectionSort(arr: number[]): number[] {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换元素
        }
    }
    return arr;
}

// 示例
const array = [3, 6, 8, 10, 1, 2, 1];
console.log("Original array:", array);
const sortedArray = selectionSort(array);
console.log("Sorted array:", sortedArray);

希尔排序

核心思想

希尔排序首先设定一个“间隔”，开始时为数组长度的一半，对每个间隔内的元素进行插入排序，然后将间隔减半，再进行插入排序，直到间隔为1，此时的插入排序已经是对整个数组进行排序了。

// npm run code src/code/algorithm/shell-sort.ts

export { };

function shellSort(arr: number[]): number[] {
    let n = arr.length;
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < n; i += 1) {
            let temp = arr[i];
            let j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
    return arr;
}

// 示例
const array = [3, 6, 8, 10, 1, 2, 1];
console.log("Original array:", array);
const sortedArray = shellSort(array);
console.log("Sorted array:", sortedArray);