【金九银十】笔试通关 + 小学生都能学会的快速排序

算法原理

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略来对数组进行排序。它的核心思想是通过一趟排序将待排序的数组分成两部分，其中一部分的所有元素比另一部分的所有元素都要小，然后递归地对这两部分分别进行快速排序，直到整个序列有序。

步骤如下

选择基准（Pivot）: 从数组中选择一个元素作为基准（通常选择第一个元素、最后一个元素或中间元素）。
分区（Partition）: 将数组重新排列，所有小于基准的元素放在基准的左边，所有大于基准的元素放在基准的右边。
递归排序: 对基准左边的子数组和右边的子数组分别进行快速排序。
组合结果: 递归结束后，整个数组就已经排好序。

实例分析

假设我们要对以下数组进行快速排序：

[3, 6, 8, 10, 1, 2, 1]

步骤如下：

选择基准: 选择第一个元素 3 作为基准。
分区: 重新排列数组，使得比 3 小的元素在其左边，比 3 大的元素在其右边。结果可能是 [1, 2, 1, 3, 6, 8, 10]。
递归排序: 现在对 [1, 2, 1] 和 [6, 8, 10] 分别进行快速排序。
对 [1, 2, 1] 选择 1 作为基准，重新排列得到 [1, 1, 2]。
对 [6, 8, 10] 选择 6 作为基准，重新排列得到 [6, 8, 10]。
组合结果: 最终结果为 [1, 1, 2, 3, 6, 8, 10]。

动态实现

代码语言：javascript复制

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Quick Sort Visualization</title>
    <style>
        body {
            font-family: Arial, sans-serif;
            background-color: #f4f4f4;
            margin: 0;
            padding: 20px;
            display: flex;
            flex-direction: column;
            align-items: center;
        }

        h2 {
            color: #333;
            margin-bottom: 20px;
        }

        #array-container {
            display: flex;
            justify-content: center;
            align-items: flex-end;
            height: 300px;
            margin-bottom: 20px;
            border: 1px solid #ccc;
            background-color: #fff;
            padding: 30px;
            border-radius: 8px;
            box-shadow: 0 4px 8px rgba(0, 0, 0, 0.1);
        }

        .array-bar {
            display: flex;
            justify-content: center;
            align-items: flex-end;
            margin: 0 2px;
            background-color: teal;
            border-radius: 4px;
            position: relative;
            transition: height 0.3s;
        }

        .array-bar p {
            margin: 0;
            color: rgb(228, 28, 28);
            font-weight: bold;
            font-size: 14px;
            position: absolute;
            bottom: -20px;
        }

        button {
            padding: 10px 20px;
            font-size: 16px;
            color: #fff;
            background-color: teal;
            border: none;
            border-radius: 4px;
            cursor: pointer;
            transition: background-color 0.3s;
        }

        button:hover {
            background-color: #005f5f;
        }
    </style>
</head>
<body>
    <h2>Quick Sort Visualization</h2>
    <div id="array-container"></div>
    <button onclick="quickSort(array, 0, array.length - 1)">Start Quick Sort</button>

    <script>
        // Initial Array
        let array = [3, 6, 8, 10, 1, 2, 1];
        const container = document.getElementById("array-container");

        // Function to create bars for visualization
        function createBars(array) {
            container.innerHTML = '';
            for (let i = 0; i < array.length; i  ) {
                const bar = document.createElement('div');
                bar.className = 'array-bar';
                bar.style.height = `${array[i] * 20}px`;
                bar.style.width = '40px';

                const number = document.createElement('p');
                number.textContent = array[i];
                bar.appendChild(number);

                container.appendChild(bar);
            }
        }

        // Quick Sort Implementation
        async function quickSort(arr, low, high) {
            if (low < high) {
                let pi = await partition(arr, low, high);
                await quickSort(arr, low, pi - 1);
                await quickSort(arr, pi   1, high);
            }
            createBars(arr);
        }

        async function partition(arr, low, high) {
            let 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]];
                    createBars(arr);
                    await new Promise(resolve => setTimeout(resolve, 300));
                }
            }
            [arr[i   1], arr[high]] = [arr[high], arr[i   1]];
            createBars(arr);
            await new Promise(resolve => setTimeout(resolve, 300));
            return i   1;
        }

        // Initialize bars
        createBars(array);
    </script>
</body>
</html>

代码分析

代码语言：javascript复制

async function quickSort(arr, low, high) {
    if (low < high) {
        let pi = await partition(arr, low, high);
        await quickSort(arr, low, pi - 1);
        await quickSort(arr, pi   1, high);
    }
    createBars(arr);
}

quickSort(arr, low, high) 函数

参数说明:

代码语言：javascript复制

- `arr`: 需要排序的数组。
- `low`: 数组的起始索引（即子数组的第一个元素的索引）。
- `high`: 数组的结束索引（即子数组的最后一个元素的索引）。

代码语言：javascript复制

async function partition(arr, low, high) {
    let 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]];
            createBars(arr);
            await new Promise(resolve => setTimeout(resolve, 300));
        }
    }
    [arr[i   1], arr[high]] = [arr[high], arr[i   1]];
    createBars(arr);
    await new Promise(resolve => setTimeout(resolve, 300));
    return i   1;
}

partition(arr, low, high) 函数

参数说明:
- arr: 需要分区的数组。
- low: 子数组的起始索引。
- high: 子数组的结束索引。
功能:
- 这是快速排序的核心部分，负责将数组 arr 按基准点 pivot 分成两个部分：左侧部分小于 pivot，右侧部分大于 pivot。
核心逻辑:
- let pivot = arr[high];：选择数组中最后一个元素作为基准点（pivot）。
- let i = low - 1;：i 指向的是比 pivot 小的元素的最后一个位置。
- for (let j = low; j < high; j )：遍历数组从 low 到 high-1 位置的所有元素。
  - if (arr[j] < pivot)：如果当前元素 arr[j] 小于 pivot，则将其与 i 1 位置的元素交换，并将 i 加 1。这样就能保证所有小于 pivot 的元素都移动到左侧。
  - createBars(arr);：每次元素交换后，更新可视化条形图，显示当前排序状态。
  - await new Promise(resolve => setTimeout(resolve, 300));：添加延迟效果，让可视化过程更清晰。
- return i 1;：返回新的基准点索引，将其用于后续递归调用。

createBars(array) 函数

代码语言：javascript复制

function createBars(array) {
    container.innerHTML = '';
    for (let i = 0; i < array.length; i  ) {
        const bar = document.createElement('div');
        bar.className = 'array-bar';
        bar.style.height = `${array[i] * 20}px`;
        bar.style.width = '40px';

        const number = document.createElement('p');
        number.textContent = array[i];
        bar.appendChild(number);

        container.appendChild(bar);
    }
}

功能:
- 该函数用于根据数组中的元素动态创建对应的条形图，展示数组的排序状态。
核心逻辑:
- container.innerHTML = '';：清空容器中的现有内容，为新条形图腾出空间。
- for (let i = 0; i < array.length; i )：遍历数组中的每个元素，为其创建一个条形图。
  - const bar = document.createElement('div');：为数组中的每个元素创建一个 div 元素，用于表示条形图。
  - bar.style.height =${arrayi * 20}px;：根据数组元素的值设置条形图的高度。
  - const number = document.createElement('p');：创建一个 p 元素，用于显示条形图下方的数字。
  - bar.appendChild(number);：将数字添加到条形图中。
  - container.appendChild(bar);：将条形图添加到容器中，显示在页面上。

通过这些函数的配合，快速排序算法能够不仅高效地对数组进行排序，还能实时地动态展示排序过程，使算法的执行过程更加直观。

腾讯技术创作特训营S9金九银十快速排序

0 人点赞