JavaScript 中的快速排序算法

什么是排序？

排序就是将元素按我们想要的顺序排列。您可能在学校或大学时期遇到过这种情况。例如，将数字从小到大（升序）或从大到小（降序）排列，这就是我们到目前为止看到的，并且称为排序。

JavaScript 中的默认排序

如前所述，JavaScript 有 sort()。让我们以一个包含数组元素的例子，如 [5,3,7,6,2,9]，并希望将这些数组元素按升序排序。只需在 items 数组上调用 sort()，它就会按升序对数组元素进行排序。

代码

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

在 JavaScript 中选择快速排序而非默认 sort() 的原因是什么？

虽然 sort() 给出了我们想要的结果，但问题在于它排序数组元素的方式。JavaScript 中的默认 sort() 使用 Chrome 的 V8 引擎的插入排序，以及Mozilla Firefox 和Safari 的归并排序。

但是，除此以外，如果您需要对大量元素进行排序，这是不合适的。所以，解决方案是为大型数据集使用快速排序。

因此，要完全理解，您需要知道快速排序如何工作，让我们现在详细看一下。

什么是快速排序？

快速排序遵循分而治之算法。它根据某些条件将元素分成更小的部分，并在这些分割的小部分上执行排序操作。因此，它适用于大型数据集。所以，以下是快速排序工作步骤的简单说明。

1. 首先选择一个将被称为枢轴元素的元素。
2. 接下来，将所有数组元素与选定的枢轴元素进行比较，并以这样的方式排列它们：小于枢轴元素的元素在其左侧，大于枢轴的元素在其右侧。
3. 最后，对枢轴元素左右两侧的元素执行相同的操作。

所以，这是快速排序的基本概述。以下是执行快速排序需要一个接一个遵循的步骤。

快速排序如何工作

1. 首先找到数组中的“枢轴”元素。
2. 将左指针设置为数组的第一个元素。
3. 将右指针设置为数组的最后一个元素。
4. 比较左指针指向的元素，如果它小于枢轴元素，则将左指针向右移动（左索引加 1）。继续此操作，直到左侧元素大于或等于枢轴元素。
5. 比较右指针指向的元素，如果它大于枢轴元素，则将右指针向左移动（右索引减 1）。继续此操作，直到右侧元素小于或等于枢轴元素。
6. 检查左指针是否小于或等于右指针，然后交换这些指针位置中的元素。
7. 递增左指针并递减右指针。
8. 如果左指针的索引仍小于右指针的索引，则重复该过程；否则，返回左指针的索引。

因此，让我们通过一个例子来看看这些步骤。让我们考虑需要排序的元素数组是 [5,3,7,6,2,9]。

确定枢轴元素

但在继续快速排序之前，选择枢轴元素起着重要作用。如果您选择第一个元素作为枢轴元素，那么它在排序后的数组中会给出最差的性能。因此，建议始终选择中间元素（数组长度除以 2）作为枢轴元素，我们也是这样做的。

以下是使用示例 [5,3,7,6,2,9] 进行快速排序的步骤。

步骤 1：将中间元素确定为枢轴。因此，7 是枢轴元素。

步骤 2：将左指针和右指针分别设置为数组的第一个和最后一个元素。因此，左指针指向索引 0 处的5，右指针指向索引 5 处的9。

步骤 3：将左指针处的元素与枢轴元素进行比较。由于 5 < 6，将左指针移到右侧索引 1。

步骤 4：现在，仍然 3 <6，所以将左指针移到右侧一个索引。所以现在 7 > 6，停止递增左指针，现在左指针位于索引 2。

步骤 5：现在，将右指针处的值与枢轴元素进行比较。由于 9 > 6，将右指针移到左侧。现在，因为 2 < 6，停止移动右指针。

步骤 6：交换左右指针处的两个值。

步骤 7：再将两个指针各移动一步。

步骤 8：由于 6 = 6，将指针再移一步，然后停止，因为左指针越过了右指针，并返回左指针的索引。

因此，根据上述方法，我们需要为交换元素和根据上述步骤对数组进行分区编写代码。

在 JavaScript 中交换两个数字的代码

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); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

执行递归操作

执行上述步骤后，将返回左指针的索引，我们需要使用它来分割数组并对该部分执行快速排序。因此，它被称为分而治之算法。

因此，快速排序将一直执行，直到左数组和右数组中的所有元素都已排序。

注意：快速排序是在同一数组上执行的，在此过程中不会创建新数组。

因此，我们需要调用上面解释的partition()，并根据它将数组分割成部分。所以这里是您使用它的代码，

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 result = quickSort(items, 0, items.length - 1);

完整的快速排序代码

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); //sawpping 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); //prints [2,3,5,6,7,9]

注意：快速排序的时间复杂度为O(nlogn)。