Javascript 中的快速排序

达到完美境界并不是无以复加，而是无可去除。——<安托万·德·圣·埃克苏佩里>

介绍

排序是指按特定顺序（数字或字母顺序）排列列表中的项目。排序通常与搜索一起使用。

多年来，已经开发了许多排序算法，迄今为止最快的算法之一是Quicksort。

快速排序使用分而治之的策略对给定的元素列表进行排序。这意味着算法将问题分解为子问题，直到它们变得足够简单以直接解决。

从算法上讲，这可以递归或迭代地实现。然而，递归方法对于这个问题更自然。

理解快速排序背后的逻辑

让我们来看看快速排序是如何工作的：

选择数组的一个元素。此元素通常称为枢轴。大多数情况下，此元素是数组中的第一个或最后一个元素。
然后，重新排列数组的元素，使枢轴左侧的所有元素都小于枢轴，而右侧的所有元素都大于枢轴。该步骤称为分区。如果一个元素等于枢轴，它在哪一边并不重要。
3.对枢轴的左侧和右侧分别重复此过程，直到对数组进行排序。

快速排序在 JavaScript 中的实现

正如我们所见，该算法的骨干是分区步骤。无论我们使用递归还是迭代方法，这一步都是相同的。

考虑到这一点，让我们首先将代码写入partition()数组：

function partition(arr, start, end){
    // Taking the last element as the pivot
    const pivotValue = arr[end];
    let pivotIndex = start; 
    for (let i = start; i < end; i++) {
        if (arr[i] < pivotValue) {
        // Swapping elements
        [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
        // Moving to next element
        pivotIndex++;
        }
    }
    
    // Putting the pivot value in the middle
    [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]] 
    return pivotIndex;
};

在这里，我们将最后一个元素作为枢轴。我们正在使用一个变量 pivotIndex 来跟踪“中间”位置，其中左侧的所有元素都较少，而右侧的所有元素都大于 pivotValue.

作为最后一步，我们将枢轴（本例中的最后一个元素）与 pivotIndex. 因此，最终，我们的枢轴元素将位于“中间”。所有元素小于其左侧的枢轴，所有元素大于或等于枢轴右侧的枢轴。

递归实现

现在我们有了这个 partition() 函数，我们必须递归地分解这个问题并应用分区逻辑来完成剩下的步骤：

function quickSortRecursive(arr, start, end) {
    // Base case or terminating case
    if (start >= end) {
        return;
    }
    
    // Returns pivotIndex
    let index = partition(arr, start, end);
    
    // Recursively apply the same logic to the left and right subarrays
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end);
}

在这个函数中，我们首先对数组进行分区。之后，我们对左右子数组进行分区。只要该方法接收到一个不为空或具有多个元素的数组，我们就会重复这一过程。

这是因为空数组和只有一个元素的数组被视为已排序。

让我们通过调用在原始示例中测试此代码：

array = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortRecursive(array, 0, array.length - 1)

console.log(array)
// 输出：
// -4,-2,0,1,2,4,5,6,7

迭代实现

正如我们之前提到的，快速排序的递归方法要直观得多。但是，迭代实施 Quicksort 是软件工程师比较常见的面试问题。

与大多数递归到迭代的转换一样，首先应该想到的是使用堆栈来模拟递归调用。这样做是为了我们可以重用一些我们熟悉的递归逻辑，并在迭代设置中使用它。

我们需要以某种方式跟踪我们还剩下哪些未排序的子数组。一种方法是简单地在堆栈中保留“成对”元素，表示给定的未排序子数组的 start 和 end。

JavaScript 没有明确的堆栈数据结构，但数组支持 push() 和 pop() 函数。然而，它们不支持peek()函数，因此我们必须使用 stack[stack.length - 1].

我们将使用与 partition 递归方法相同的函数。让我们看看如何编写 Quicksort 部分：

function quickSortIterative(arr) {
    // Creating an array that we'll use as a stack, using the push() and pop() functions
    stack = [];
    
    // Adding the entire initial array as an "unsorted subarray"
    stack.push(0);
    stack.push(arr.length - 1);
    
    // There isn't an explicit peek() function
    // The loop repeats as long as we have unsorted subarrays
    while(stack[stack.length - 1] >= 0){
        
        // Extracting the top unsorted subarray
    	end = stack.pop();
        start = stack.pop();
        
        pivotIndex = partition(arr, start, end);
        
        // If there are unsorted elements to the "left" of the pivot,
        // we add that subarray to the stack so we can sort it later
        if (pivotIndex - 1 > start){
        	stack.push(start);
            stack.push(pivotIndex - 1);
truetrue}
        
        // If there are unsorted elements to the "right" of the pivot,
        // we add that subarray to the stack so we can sort it later
        if (pivotIndex + 1 < end){
        	stack.push(pivotIndex + 1);
            stack.push(end);
        }
    }
}

测试此代码：

ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortIterative(ourArray)

console.log(ourArray)
// 输出：
// -4,-2,0,1,2,4,5,6,7

快速排序的可视化

当谈到排序算法时，将它们可视化总是好的。它只是帮助我们“看到”它们的实际效果下面是 Quicksort 算法如何工作的一个例子
资料来源：维基百科-https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif

快速排序的效率

现在我们知道如何实现快速排序算法，让我们讨论时间和空间复杂度。快速排序的最坏情况时间复杂度是 O(n 2 )。平均情况时间复杂度为 O(nlogn)。通常通过使用随机版本的快速排序来避免最坏的情况。

快速排序算法的弱点是枢轴的选择。每次选择一个错误的主元（大于/小于大多数元素），会给我们带来最坏情况下的时间复杂度。虽然重复选择一个具有大致相等数量的小于/大于主元的元素的主元会给我们带来 O(nlogn)的时间复杂度。

快速排序是其中平均情况运行时间实际上很重要的算法之一。从经验上看，无论采用何种枢轴选择策略，Quicksort 的运行时间都倾向于O(nlogn)。

此外，在空间复杂度方面，Quicksort 不会占用任何额外空间（不包括为递归调用保留的空间）。这些类型的算法在技术上称为就地算法。我们不需要额外的空间，因为我们在同一个数组上执行操作。

总结

在本文中，我们回顾了 Quicksort 背后的理论，然后使用 JavaScript 递归和迭代地实现了它。

参考

https://stackabuse.com/quicksort-in-javascript

关注【公众号】，了解更多。

赏

支付宝打赏

微信打赏

赞赏一下坚持原创技术分享，您的支持将鼓励我继续创作！

介绍