当前位置：首页 > JavaScript

js用栈实现排序

2026-01-31 04:57:47JavaScript

使用栈实现排序的方法

在JavaScript中，可以通过栈（Stack）的特性实现排序功能。以下是两种常见的基于栈的排序方法：单调栈排序和模拟递归排序。

单调栈排序

单调栈是一种特殊的栈结构，栈内元素保持单调递增或递减的顺序。通过单调栈可以实现对数组的排序。

function sortWithStack(arr) {
    const stack = [];
    const tempStack = [];

    for (const num of arr) {
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            tempStack.push(stack.pop());
        }
        stack.push(num);
        while (tempStack.length > 0) {
            stack.push(tempStack.pop());
        }
    }

    return stack;
}

// 示例
const arr = [5, 3, 8, 1, 2];
console.log(sortWithStack(arr)); // 输出 [8, 5, 3, 2, 1]

说明：

主栈stack用于存储排序后的结果。
辅助栈tempStack用于临时存放需要调整顺序的元素。
每次将元素压入主栈时，确保主栈的栈顶元素始终比当前元素大（或小），否则将栈顶元素弹出到辅助栈中。

模拟递归排序（类似快速排序）

通过两个栈模拟递归调用的过程，实现类似快速排序的分治策略。

function quickSortWithStack(arr) {
    const stack = [];
    stack.push(0);
    stack.push(arr.length - 1);

    while (stack.length > 0) {
        const high = stack.pop();
        const low = stack.pop();

        if (low < high) {
            const pivotIndex = partition(arr, low, high);
            stack.push(low);
            stack.push(pivotIndex - 1);
            stack.push(pivotIndex + 1);
            stack.push(high);
        }
    }

    return arr;
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }

    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

// 示例
const arr = [5, 3, 8, 1, 2];
console.log(quickSortWithStack(arr)); // 输出 [1, 2, 3, 5, 8]

说明：