各种排序算法的typescript实现

选择排序

/* 选择排序 */
function selectionSort(nums: number[]): void {
    let n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (let i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        let k = i;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[k]) {
                k = j; // 记录最小元素的索引
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        [nums[i], nums[k]] = [nums[k], nums[i]];
    }
}

冒泡排序

// 双重循环 内部for首先第0和第1,第1和第2...依次比较一遍,同时将大的值互换到后面 
// 外层for保证内部每遍历完一次,当前最大值就处于最右侧,同时下次冒泡遍历时就不需要当前最后一项了 
function bubble_sort(arr: number[]): void {
    const ll = arr.length
    for(let i = 0; i < ll - 1; i++){
        let swapped = false;   // 优化标志
        for(let j = 0; j < ll-1-i; j++){
            if(arr[j] > arr[j+1]){
                [arr[i], arr[j+1]] = [arr[j+1], arr[i]]
                swapped = true
            }
        }
        /*  如果某一轮冒泡过程中完全没有发生任何交换，就说明整个数组已经有序了，后面的所有轮次都不需要再执行了。 
        在数组已经有序或接近有序时，效率大幅提升（从 O(n²) 变成 O(n)） 如果这一轮没有发生任何交换，说明数组已经有序，可以提前结束  
         */
        if (!swapped) break;
    }
}

插入排序

/* 插入排序 */
function insertionSort(nums: number[]): void {
    // 外循环：已排序区间为 [0, i-1]
    for (let i = 1; i < nums.length; i++) {
        const base = nums[i];
        let j = i - 1;
        // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
            j--;
        }
        nums[j + 1] = base; // 将 base 赋值到正确位置
    }
}

快速排序: 通过基准值和分治法, 递归处理

/**   取数组最后一项作为基准值 则左边n-1项作为数组开始遍历,进行分区,此时操作的是原数组  
      完整遍历实现目的:1.当当前项是小于基准值,将i标志位右移一位,代表左侧是小于基准的数组的一部分 
                    2.遇到大于基准值的不管(此时首个大于基准值的项为i+1),继续找到小于的项,将小于的项与i+1项互换位置 
                    3. 最终的i+1就是首个大于基准值的项,此时将基准值与这一项交换位置,从而切分出左右2个新数组(分治法实现log n)
      至此得到新基准值的索引,并且左侧都是小值,右侧都是大值, 递归调用排序函数2遍,第一次传入左侧数组参数,第二次传入右侧数组参数; 数组为空或只有一项时或者两个值相等时跳出递归
      通过原地交换值, 最小化空间复杂度
*/

function quickSortInPlace<T>(arr: T[], low: number = 0, high: number = arr.length - 1): void {
    if (low < high) {
        const pivotIndex = partition(arr, low, high);
        quickSortInPlace(arr, low, pivotIndex - 1);
        quickSortInPlace(arr, pivotIndex + 1, high);
    }
}

// 分区函数（核心）原地分割
function partition<T>(arr: T[], low: number, high: number): number {
    const pivot = arr[high];        // 选择最后一个元素作为基准
    let i = low - 1;                // i 为小于 pivot 的元素的最后一个位置
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];  // 交换
        }
    }
    // 将 pivot 放到正确的位置
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}
// 使用示例
const numbers = [64, 34, 25, 12, 22, 11, 90, 88, 45];
console.log("排序前:", numbers);
quickSortInPlace(numbers);
console.log("排序后:", numbers);

归并排序

/* 合并左子数组和右子数组 */
function merge(nums: number[], left: number, mid: number, right: number): void {
    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    const tmp = new Array(right - left + 1);
    // 初始化左子数组和右子数组的起始索引
    let i = left,
        j = mid + 1,
        k = 0;
    // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

/* 归并排序 */
function mergeSort(nums: number[], left: number, right: number): void {
    // 终止条件
    if (left >= right) return; // 当子数组长度为 1 时终止递归
    // 划分阶段
    let mid = Math.floor(left + (right - left) / 2); // 计算中点
    mergeSort(nums, left, mid); // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并阶段
    merge(nums, left, mid, right);
}

归并排序

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
function siftDown(nums: number[], n: number, i: number): void {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        let l = 2 * i + 1;
        let r = 2 * i + 2;
        let ma = i;
        if (l < n && nums[l] > nums[ma]) {
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]) {
            ma = r;
        }
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma === i) {
            break;
        }
        // 交换两节点
        [nums[i], nums[ma]] = [nums[ma], nums[i]];
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
function heapSort(nums: number[]): void {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (let i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}

桶排序

/* 桶排序 */
function bucketSort(nums: number[]): void {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    const k = nums.length / 2;
    const buckets: number[][] = [];
    for (let i = 0; i < k; i++) {
        buckets.push([]);
    }
    // 1. 将数组元素分配到各个桶中
    for (const num of nums) {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        const i = Math.floor(num * k);
        // 将 num 添加进桶 i
        buckets[i].push(num);
    }
    // 2. 对各个桶执行排序
    for (const bucket of buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        bucket.sort((a, b) => a - b);
    }
    // 3. 遍历桶合并结果
    let i = 0;
    for (const bucket of buckets) {
        for (const num of bucket) {
            nums[i++] = num;
        }
    }
}