javascript排序_通过JavaScript了解快速排序

喜欢ヅ旅行 2022-11-27 04:25 142阅读 0赞

javascript排序

One problem of working with [merge sorts][] is that they need to create and store so many arrays in memory with mostly the redundant data. If we’re limited on memory, we can resort to a **quick sort** to run it “in place”, meaning the changes and results all happen directly with what’s being sorted, thus saving on memory.

使用[合并排序的][merge sorts]一个问题是它们需要在内存中创建并存储如此多的数组，其中大部分都是冗余数据。 如果我们的内存有限，我们可以采用**快速排序**以使其“就地”运行，这意味着更改和结果都直接与所排序的内容有关，从而节省了内存。

## 先决条件 **(**Prerequisites**)** ##

We’re going to be going over the standard recursive version, although you can do this iteratively, so understanding how recursion works will be helpful, which you can [brush up on here][].

尽管您可以迭代执行此操作，但是我们将要遍历标准递归版本，因此了解递归的工作方式将很有帮助，您可以[在此处继续阅读][brush up on here] 。

## 概念 **(**Concept**)** ##

Quick sort is definitely one of the less intuitive algorithms, so here’s a very simple overview.

快速排序绝对是不太直观的算法之一，因此这里有一个非常简单的概述。

We select a number, called our `pivot`, which we’ll compare every number to when we loop through our items. The goal is to reorganize the array so it is partitioned into two halves, with everything in each either being less than or greater than our pivot. When the pivot is in it’s final position we’ll move on to doing the same thing with a new pivot, with every pivot being cemented in place until every item has been a pivot at least once.

我们选择一个数字，称为我们的`pivot` ，当我们遍历所有项目时，我们将其与每个数字进行比较。 目标是重组数组，以便将其分为两半，每个半数都小于或大于我们的支点。 当枢轴处于其最终位置时，我们将继续使用新的枢轴执行相同的操作，将每个枢轴固定在适当位置，直到每个项目至少成为一次枢轴为止。

Graphic/Animation thanks to [VisuAlgo.net][]

图形/动画得益于[VisuAlgo.net][]

Like merge sort, the complexity on average is O(nlogn), so it’s up to you which you prefer.

像合并排序一样，平均复杂度为O(nlogn)，所以这取决于您的偏好。

## 实践数据 **(**Practice Data**)** ##

As always, here’s an unsorted array of 50 random numbers to play with. I also recommend looking into JavaScript’s [performance api][] to compare it to other algorithms and with different data.

与往常一样，这是一个由50个随机数组成的未排序数组，可以使用。 我还建议研究JavaScript的[性能api，][performance api]以将其与其他算法和不同数据进行比较。

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

## 枢 **(**Pivot**)** ##

Firstly, we’ll need our pivot utility function. There’s 4 main parts to this, our swapper, the loop, the pivot itself, and our pointer.

首先，我们需要我们的数据透视实用程序功能。 共有四个主要部分，我们的交换器，循环，枢轴本身和指针。

Our pointer is just a placeholder for our pivot. Every time our loop progresses, each item is compared to the pivot and if it is smaller it’s swapped with our pointer. Every time we do this is to ensure that the pointer is ahead of everything smaller than the pivot and before everything that’s larger. When everything is complete, and our array is partitioned, then we can assign the pivot to the pointer’s index as its final position.

我们的指针只是我们的支点的占位符。 每次循环执行时，会将每个项目与枢轴进行比较，如果较小，则将其与我们的指针交换。 每次执行此操作都是为了确保指针位于小于枢轴的所有物体的前面，并且位于大于枢轴的所有物体的前面。 一切完成后，对数组进行分区，然后可以将枢轴分配给指针的索引作为其最终位置。

Our swap works by just reassigning the indexes of each item with each other’s index, nothing too crazy.

我们的交换工作是通过将每个项目的索引重新分配给彼此的索引来进行的，没有什么太疯狂了。

## 快速排序 **(**Quick Sort**)** ##

Implementation is simultaneously pretty simple and a bit confusing, as recursion tends to be. We’re going to use our `pivot` function to get the first sorted item from our array. With that, we’ll recursively run our `quickSort` to do the same process on the first half of our partitioned array, which will repeat until there’s nothing left to sort, then do the same for the other half. When both are done our fully sorted array can be returned.

同时实现非常简单，而且有点令人困惑，因为递归往往会如此。 我们将使用`pivot`功能从数组中获取第一个排序的项目。 这样，我们将递归地运行`quickSort`在分区数组的前半部分执行相同的过程，该过程将重复进行直到没有剩余可排序的地方，然后再对下半部分进行相同的处理。 当两者都完成时，可以返回完全排序的数组。

const quickSort = (arr, start = 0, end = arr.length) => {
      let pivotIndex = pivot(arr, start, end);
    
      if (start >= end) return arr;
      quickSort(arr, start, pivotIndex);
      quickSort(arr, pivotIndex + 1, end);
    
      return arr;
    };
    
    console.log(quickSort(unsortedArr));

## 结论 **(**Conclusion**)** ##

Quick sort was definitely one of the most difficult sorting algorithm to wrap my head around. Between having 4 changing parts and 2 recursion stacks, this is definitely something you probably shouldn’t expect to remember perfectly and may want to bookmark for later reference.

快速排序绝对是将我的头缠起来的最困难的排序算法之一。 在具有4个变化的部件和2个递归堆栈之间，这绝对是您可能不应该期望完美记住的事情，并且可能希望添加书签以供以后参考。

> 翻译自: [https://www.digitalocean.com/community/tutorials/js-quick-sort][https_www.digitalocean.com_community_tutorials_js-quick-sort]

javascript排序

[merge sorts]: https://www.digitalocean.com/community/tutorials/js-understanding-merge-sort
[brush up on here]: https://www.digitalocean.com/community/tutorials/js-understanding-recursion
[VisuAlgo.net]: https://visualgo.net
[performance api]: https://www.digitalocean.com/community/tutorials/js-js-performance-api
[https_www.digitalocean.com_community_tutorials_js-quick-sort]: https://www.digitalocean.com/community/tutorials/js-quick-sort