快速排序算法 Java示例脚本

什么是快速排序？

快速排序 是一种比较排序算法，它遵循以下规则： 分而治之 该方法选择一个元素作为基准元素，将数组分成包含小于基准元素的值的部分和包含大于基准元素的值的部分，然后对每个部分应用相同的过程，直到整个数组排序完成。

快速排序是所有编程语言中最广泛使用的排序算法之一。如果你写 JavaScript您可能已经使用过内置的 种类（） 因此，你可能会好奇为什么学习单独的快速排序实现是值得的。要回答这个问题，你首先需要了解排序的含义以及默认排序算法是什么。 Java脚本确实做到了。

快速排序具备以下三个特性：

• 就位： 它重新排列了原有内容。 排列 并且不会分配第二个相同大小的数组。
• 递归： 每个分区都会产生两个较小的范围，这两个范围按相同的函数排序。
• 不稳定： 具有相同键的两个元素最终的相对顺序可能与它们最初的相对顺序不同。

什么是排序？

排序是指按照特定的顺序排列元素。你几乎肯定在学校里学过：把数字从小到大排列就是排序。 升序 按顺序，并按从大到小的顺序排列是 降 排序不仅限于数字。字符串可以按字母顺序排序，日期可以按时间顺序排序，对象还可以按您选择的任何字段排序，例如价格或分数。

排序至关重要，因为有序数据可以带来更快的操作速度。二分查找的时间复杂度为 O(log n)，但前提是输入数据必须已排序。一旦数据有序化，去重、范围查询、排名和合并操作的效率都会大幅提升，这也是为什么每种编程语言都至少提供一种排序函数的原因。

默认排序 Java脚本

如前面提到的， Java脚本提供 种类（）假设有一个小数组，例如 [5,3,7,6,2,9]，你想让它按升序排列。调用 种类（） 数组上的操作似乎正是如此。

上面的截图显示了浏览器控制台打印出的排序后的数组。以下是相同的代码：

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

输出：

[ 2, 3, 5, 6, 7, 9 ]

这个结果是正确的，但纯属偶然。 Array.prototype.sort() 将每个元素转换为字符串并比较这些字符串。 除非你提供一个比较函数。这个数组中的每个值都是一个数字，所以字符串的顺序恰好与数字的顺序一致。如果更改数据，这种错觉就会消失。

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

输出：

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

sort()函数使用的是哪种算法？

规范中没有指定算法，因此每个引擎都自行选择。现代引擎都使用基于合并的算法：

• V8 （Chrome、Edge、Node.js）已经使用 蒂姆·索特 自 V8 7.0 起，随 Chrome 70 一起发布。
• 蜘蛛猴 (Firefox）用途 合并排序.
• Java脚本核心 （Safari 也使用） 合并排序.

自 ES2019 起，该语言保证了这一点。 sort() is 稳定这就排除了在引擎内部使用简单的快速排序。基于归并的排序需要 O(n) 的辅助内存，并且必须调用你的算法。 Java每个比较都使用脚本比较器。手写的数值快速排序算法直接比较数字并进行原地排序，因此在大数值数组上也能取得好成绩。在 Node.js 22 上对 1,000,000 个随机整数进行排序大约需要 O(n) 时间。 100毫秒 使用下面的快速排序，大致 210毫秒 - sort((a, b) => a - b).

因此，当你需要原地排序、严格控制内存使用，或者只是想深入了解排序原理时，编写快速排序算法是值得的。让我们详细了解一下它的机制。

快速排序的工作原理是什么？

快速排序重复执行一个核心操作，即 分割范围越来越小。以下是具体步骤：

1. 为您的 枢纽 数组中的元素。
2. 将左指针指向范围的第一个元素。
3. 将右指针指向范围的最后一个元素。
4. 将左指针指向的元素与基准元素进行比较。如果左指针指向的元素小于基准元素，则将左指针向右移动一步。重复此过程，直到左指针指向的元素大于或等于基准元素为止。
5. 将右指针指向的元素与基准元素进行比较。如果右指针指向的元素大于基准元素，则将右指针向左移动一位。重复此过程，直到右指针指向的元素小于或等于基准元素为止。
6. 如果左指针仍然小于或等于右指针，则交换这两个元素。
7. 增加左指针并减少右指针。
8. 如果左索引仍然小于或等于右索引，则从步骤 4 开始重复。否则，返回左指针的索引。

上图 trac这些指针移动发生在一个示例数组上。所有小于基准元素的元素最终都会移动到基准元素的左侧，所有大于基准元素的元素最终都会移动到基准元素的右侧，这与返回的索引所标记的内容完全一致。下面的部分将逐步遍历同一个数组。

如何确定枢轴元素

选择枢轴点是区分快速排序和慢速排序的关键所在。如果你总是选择…… 第一 对于一个已经排序的数组，如果只包含一个元素，就会产生最糟糕的分割结果：一边为空，另一边包含所有剩余元素。这使得算法的时间复杂度变为 O(n²)。 中间 元素（数组长度除以二）避免了对已排序和已逆排序输入的该陷阱，这就是为什么下面的代码使用它的原因。

常见的转型策略：

• 第一个或最后一个元素： 代码最简单，但对已排序数据的时间复杂度为 O(n²)。
• 中间元素： 一个好的默认值，可以在 O(n log n) 内处理已排序和已逆排序的数组。
• 随机元素： 使得预先构建最坏情况输入变得不可能。
• 中位数为三： 取第一个值、中间值和最后一个值的中位数；这是生产库中的标准选择。

现在来看一下数组上的快速排序。 [5,3,7,6,2,9].

步骤1： 枢轴点是中间元素。当 left = 0 且 right = 5 时， Math.floor((5 + 0) / 2) 给出的索引为 2，因此枢轴值为 7.

步骤2： 指针从数组的两端开始。左指针位于索引 0（值）。 5）并且右指针位于索引 5（值） 9).

步骤3： 将左侧的值与枢轴值进行比较。5 < 7，所以向右移动到索引 1。3 < 7，所以向右移动到索引 2。那里的值为 7，不小于枢轴值，因此左侧指针停止在索引 2。

步骤4： 将右指针的值与枢轴值进行比较。9 > 7，因此向左移动到索引 4。该值为 2，不大于枢轴值，所以右指针停止在索引 4。

步骤5： 左索引 (2) 小于或等于右索引 (4)，因此交换这两个值。数组变为 [5,3,2,6,7,9].

步骤6： 将两个指针都向内移动一步。现在左指针位于索引 3，右指针也位于索引 3。

步骤7： 重复扫描。索引 3 处的值为 6，且 6 < 7，因此左指针移动到索引 4。索引 3 处的值不大于枢轴值，因此右指针保持在索引 3。

步骤8： 左侧索引 (4) 现在大于右侧索引 (3)，因此循环结束，函数返回。 4索引 4 之前的所有值都小于或等于枢轴值，索引 4 之后的所有值都大于或等于枢轴值。

根据该步骤，你需要编写两个操作的代码：交换ping 两个元素和一个范围的划分。

Code 交换两个 Numbers in Java脚本

如上图所示，交换辅助函数使用一个临时变量来交换两个索引处的值。它直接修改数组，不返回任何值。

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

输出：

[ 9, 3, 7, 6, 2, 5 ]

Code 执行分区

上面截图中的代码将步骤 1 到 8 转换成了一个函数。两个内部 循环 推进指针， if 代码块执行交换操作，函数返回拆分后的索引。

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

输出：

[ 5, 3, 2, 6, 7, 9 ]
4

输出结果与手动操作步骤完全一致：经过一次分区后，数组为 [5,3,2,6,7,9]，返回的分割索引为 4。

执行递归 OperaTION

分区返回分割索引后，使用该索引将范围分割成两部分，并对每一半执行快速排序。这就是它被称为分治算法的原因。递归过程会一直持续，直到每个子范围都只包含一个元素，此时整个数组就排序完成了。

注意： 快速排序始终在同一个数组上进行操作。过程中不会创建新的数组，因此它是一种原地排序算法。

所以你打电话给 划分（） 上述函数及其返回值用于拆分 排列 将其分成几部分。以下是实现此功能的代码：

请注意截图中突出显示的两个守卫条件。 left < index - 1 确认左侧至少还剩下两个元素，并且 index < right 右侧的情况也一样。如果没有这些保护措施，该函数会在处理单元素范围时无限循环调用自身。

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

输出：

[ 2, 3, 5, 6, 7, 9 ]

完成快速排序 Code

将交换、分区和递归部分组合在一起，就得到了完整的实现：

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

输出：

[ 2, 3, 5, 6, 7, 9 ]

上面的截图显示了编辑器中的完整程序以及控制台中已排序的数组。该实现已针对已排序数组、反向排序数组、包含重复值和相同值的数组、负数数组、单个元素数组和空数组进行了验证，在所有情况下均返回了正确的结果。

快速排序的时间复杂度和空间复杂度

每次分区都会遍历范围内的每个元素一次，因此单次遍历的时间复杂度为 O(n)。总时间复杂度取决于数组在范围变得无关紧要之前可以分割多少次。

空间复杂度为 O(log n) 对于这种原地调用版本，由于没有分配第二个数组，因此唯一额外的内存就是递归栈，而均衡拆分机制使得该栈的深度约为 log₂(n) 帧。在最坏情况下，栈会增长到 O(n) 帧，这就是为什么非常大的数组会导致调用栈溢出的原因。

两个数字可以具体说明这一点。使用上述代码对 4,096 个随机值进行排序，大约需要 65,000 次比较，而理论比较次数为 n·log₂(n) 49,152 次；最深的递归遍历了 24 帧，而 log₂(4096) 为 12。这两个数字都符合 O(n log n) 算法预期的较小常数因子。

快速排序与其他排序方式的比较 Algorithms

快速排序很少是唯一选择。下表将其与其他最可能遇到的算法进行比较，以便您可以根据数据选择合适的算法。

快速排序在实践中通常更胜一筹，因为它内部循环紧凑，并且适用于缓存友好的连续范围。当需要保证 O(n log n) 的时间复杂度或稳定的排序时，选择归并排序；当内存极其有限时，选择堆排序；对于非常小或接近有序的数组，选择插入排序。生产环境中的库经常将它们结合起来使用：例如，introsort 先使用快速排序，如果递归过深则切换到堆排序，最后在小范围内使用插入排序完成排序。

如何快速对对象和字符串进行排序

目前展示的实现方法是将值与……进行比较 < 和 >这就将其限制为数字。实际应用需要排序。 对象 按属性、字符串字母顺序或日期时间顺序进行比较。解决方法是将比较操作移至回调函数中，就像内置函数那样。 sort() 一样。

比较器接收两个值，当第一个值应该在前时返回负数，当第二个值应该在前时返回正数，当两个值相等时返回零。用比较器调用替换两个硬编码的比较操作，使得该算法能够处理任何数据类型。

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

输出：

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

有三点值得注意。递归保护现在是 left >= right这对于任何范围都是正确的，并且不依赖于外部数组的长度。字符串比较使用 localeCompare() 这样就能正确处理带重音符号的字符和大小写，而不是直接使用原始代码点。而且由于快速排序不稳定，薪资相同的记录可能会互换位置；如果您在意原始顺序，可以使用第二个键来打破平局。

准备好继续了吗？通过以下方式加强基本功： Java剧本简介练习指针操作 Java脚本循环继续深入研究 实际 Java脚本代码示例比较实现方式 插入排序 和 堆排序或者，也可以向此算法添加静态类型。 TypeScript 参考。

常见问题