各大排序算法

[skypesky]

[skypesky]

请实现一个快速排序

• 快速排序,错误的实现

function quickSort(nums: number[], leftBound: number, rightBound: number): void {
    if (leftBound < rightBound) {
        const midBound: number = quickSortOneStep(nums, leftBound, rightBound);
        quickSort(nums, leftBound, midBound - 1);
        quickSort(nums, midBound + 1, rightBound);
    }
}

function quickSortOneStep(nums: number[], leftBound: number, rightBound: number): number {
    if (leftBound >= rightBound) {
        return leftBound;
    }
    let midValue: number = nums[(leftBound + rightBound) >>> 1];
    console.log({ midValue });
    while (leftBound < rightBound) {
        while (leftBound < rightBound && nums[rightBound] >= midValue) {
            --rightBound;
        }
        while (leftBound < rightBound && nums[leftBound] <= midValue) {
            ++leftBound;
        }
        if (leftBound === rightBound) {
            break;
        }
        [
            nums[leftBound],
            nums[rightBound],
        ] = [
                nums[rightBound],
                nums[leftBound],
            ];
    }
    nums[leftBound] = midValue;
    return leftBound;
}
const nums: number[] = [4, 3, 45, 38, 3, 2, 1];
console.log(quickSort(nums, 0, nums.length - 1));
console.log(nums);

• 正确的姿势

import { assert } from "console";

function quickSort(nums: number[], leftBound: number, rightBound: number): void {
    if (leftBound < rightBound) {
        const midBound: number = quickSortOneStep(nums, leftBound, rightBound);
        quickSort(nums, leftBound, midBound - 1);
        quickSort(nums, midBound + 1, rightBound);
    }
}

function quickSortOneStep(nums: number[], leftBound: number, rightBound: number): number {
    if (leftBound >= rightBound) {
        return leftBound;
    }
    const value: number = nums[leftBound];
    while (leftBound < rightBound) {
        while (leftBound < rightBound && nums[rightBound] >= value) {
            --rightBound;
        }
        nums[leftBound] = nums[rightBound];
        while (leftBound < rightBound && nums[leftBound] <= value) {
            ++leftBound;
        }
        nums[rightBound] = nums[leftBound];
    }
    nums[leftBound] = value;
    return leftBound;
}
const useCases = [
    [4, 3, 2, 1],
    [1, 2, 3, 4],
    [1],
    [4, 3, 3, 3, 1],
    [1, 2],
    [2, 1],
    [3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321]
]
for (const useCase of useCases) {
    const sorted: number[] = [...useCase].sort((a, b) => a - b);
    quickSort(useCase, 0, useCase.length - 1)
    assert(useCase.join('#') === sorted.join('#'), JSON.stringify({ useCase, sorted }))
}

[skypesky]

插入排序

import { assert } from "console";

function insertSort(nums: number[], gap: number = 1) {

    let current: number, j: number;

    for (let i = gap; i < nums.length; ++i) {
        current = nums[i];
        j = i - gap;
        while (j >= 0 && nums[j] >= current) {
            nums[j + gap] = nums[j];
            j -= gap;
        }
        nums[j + gap] = current;
    }

    return nums;
}

const useCases = [
    [4, 3, 2, 1],
    [1, 2, 3, 4],
    [1],
    [4, 3, 3, 3, 1],
    [1, 2],
    [2, 1],
    [3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321],
    [],
]
for (const useCase of useCases) {
    const sorted: number[] = [...useCase].sort((a, b) => a - b);
    insertSort(useCase);
    assert(useCase.join('#') === sorted.join('#'), JSON.stringify({ useCase, sorted }))
}

[skypesky]

堆排序实现

import { assert } from "console";

function heapSort(nums: number[]): void {
    // build heap
    for (let lastIndex: number = nums.length >> 1; lastIndex >= 0; --lastIndex) {
        maxHeapify(nums, lastIndex, nums.length);
    }
    // heap sort
    for (let lastIndex: number = nums.length - 1; lastIndex >= 0; --lastIndex) {
        [nums[0], nums[lastIndex]] = [nums[lastIndex], nums[0]];
        maxHeapify(nums, 0, lastIndex);
    }
}

function maxHeapify(nums: number[], i: number, length: number): void {

    for (let j = i * 2 + 1; j < length; j = i * 2 + 1) {
        if (j + 1 < length && nums[j] < nums[j + 1]) {
            ++j;
        }
        if (nums[i] >= nums[j]) {
            return;
        }
        [nums[i], nums[j],] = [nums[j], nums[i]];
        i = j;
    }

}

const useCases = [
    [4, 3, 2, 1],
    [1, 2, 3, 4],
    [1],
    [4, 3, 3, 3, 1],
    [1, 2],
    [2, 1],
    [3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321]
]
for (const useCase of useCases) {
    const sorted: number[] = [...useCase].sort((a, b) => a - b);
    heapSort(useCase);
    assert(useCase.join('#') === sorted.join('#'), JSON.stringify({ useCase, sorted }))
}

[skypesky]

冒泡排序

import { assert } from "console";

function bubbleSort(nums: number[]) {

    for (let i = 1; i < nums.length; ++i) {
        let flag: boolean = true;
        for (let j = nums.length; j >= i; --j) {
            if (nums[j - 1] >= nums[j]) {
                [nums[j - 1], nums[j]] = [nums[j], nums[j - 1]];
                flag = false;
            }
        }
        if (flag) { // 如果发现没有交换过,那么说明数组已经是有序的,可以直接返回了.
            return nums;
        }
    }

    return nums;
}

const useCases = [
    [4, 3, 2, 1],
    [1, 2, 3, 4],
    [1],
    [4, 3, 3, 3, 1],
    [1, 2],
    [2, 1],
    [3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321],
    [],
]
for (const useCase of useCases) {
    const sorted: number[] = [...useCase].sort((a, b) => a - b);
    bubbleSort(useCase);
    assert(useCase.join('#') === sorted.join('#'), JSON.stringify({ useCase, sorted }))
}

[skypesky]

希尔排序

import { assert } from "console";

function hillSort(nums: number[]): number[] {

    for (let gap = nums.length >> 1; gap > 0; gap >>= 1) {
        insertSort(nums, gap);
    }

    return nums;
}

function insertSort(nums: number[], gap: number = 1): number[] {

    let current: number, j: number;

    for (let i = gap; i < nums.length; ++i) {
        current = nums[i];
        j = i - gap;
        while (j >= 0 && nums[j] >= current) {
            nums[j + gap] = nums[j];
            j -= gap;
        }
        nums[j + gap] = current;
    }

    return nums;
}

const useCases = [
    [4, 3, 2, 1],
    [1, 2, 3, 4],
    [1],
    [4, 3, 3, 3, 1],
    [1, 2],
    [2, 1],
    [3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321],
    [],
]
for (const useCase of useCases) {
    const sorted: number[] = [...useCase].sort((a, b) => a - b);
    hillSort(useCase);
    assert(useCase.join('#') === sorted.join('#'), JSON.stringify({ useCase, sorted }))
}

[skypesky]

桶排序

[skypesky]

归并排序

[skypesky]

基数排序

import { assert } from "console";

function radixSort(nums: number[]): number[] {

    // 求出最大值,它来决定到底要循环几次: 例如: max = 999 是一个3位数,所以要循环3次
    let max: number = Math.max(...nums);
    // 通过radix变量来进行十进制的位数运算
    let radix: number = 1;

    while (max > 0) {

        // 构造桶
        const buckets: number[][] = nums.reduce((buckets: number[][], num: number) => {
            const bucketIndex: number = (Math.floor(num / radix)) % 10;
            buckets[bucketIndex].push(num);
            return buckets;
        }, new Array(10).fill(null).map(value => []));

        // 清空数组
        nums.length = 0;

        // 已经排好序了,把数字收集起来
        for (const bucket of buckets) {
            for (const num of bucket) {
                nums.push(num);
            }
        }

        radix *= 10;
        max = Math.floor(max / 10);
    }

    return nums;
}

const useCases = [
    [4, 3, 2, 1],
    [1, 2, 3, 4],
    [1],
    [4, 3, 3, 3, 1],
    [1, 2],
    [2, 1],
    [3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321]
]
for (const useCase of useCases) {
    const sorted: number[] = [...useCase].sort((a, b) => a - b);
    radixSort(useCase);
    assert(useCase.join('#') === sorted.join('#'), JSON.stringify({ useCase, sorted }))
}