Having your datasets arranged all willy-nilly will only add more time and resources to manage and search through. Whether your data is sorted or not will directly affect what search methods you can use and can mean the difference between a search taking a million operations or taking 10, like with .

将数据集全部整理好只会增加更多时间和资源来管理和搜索。 数据是否排序将直接影响您可以使用的搜索方法，并且可能意味着一次搜索需要进行一百万次操作或进行一次要进行10次操作(例如之间的差异。

For simplicity’s sake, we’re only going to focus on sorting an array of numbers from least to greatest, but these algorithms are easily modifiable for other sorting goals. Keep in mind that these are more general concepts and patterns and less of a “how-to” for sorting data since your particular implementation may differ a lot but in the end it may conceptually resemble these patterns.

为简单起见，我们只专注于从最小到最大对数字数组进行排序，但是这些算法很容易针对其他排序目标进行修改。 请记住，这些是更笼统的概念和模式，而不是用于对数据进行排序的“操作方法”，因为您的特定实现可能有很大差异，但最终在概念上可能类似于这些模式。

Here’s the practice array of 50 random numbers.

这是由50个随机数组成的练习数组。

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];

先决条件 (Prerequisites)

I’m going to be looking at everything through the lens of , so understanding how complexity grows over time will be very helpful.

我将通过查看所有内容，因此了解复杂度如何随时间增长将非常有帮助。

气泡排序 (Bubble Sort)

This is the “Hello World” of sorting methods, nothing crazy but it gets the job done.

这是排序方法的“ Hello World”，虽然没什么疯狂，但可以完成工作。

For each item in the array we want to check if the next item is larger, if it is then swap their indexes in the array. To avoid recomparing sorted numbers we’ll start from the back of the array while another for loop gets the preceding number. This way all of the largest values build up, or “bubbles up”, on the end.

对于数组中的每个项目，我们要检查下一个项目是否更大，然后再交换它们在数组中的索引。 为了避免重新比较已排序的数字，我们将从数组的背面开始，而另一个for loop将获取先前的数字。 这样，所有最大的值最终都会累积或“冒泡”。

Graphic/Animation thanks to

图形/动画得益于

Our version works in reverse from the animation, but it’s close enough.

我们的版本与动画相反，但是已经足够接近了。

const bubble = arr => {  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];  for (let i = arr.length; i > 0; i--) {    for (let j = 0; j < i - 1; j++) {      if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);    };  };  return arr;};console.log(bubble(unsortedArr));

选择排序 (Selection Sort)

Selection sort works like the opposite of Bubble sort, while bubble sorting is pushing all of the largest values to the end now we’re going to push the minimum values to the start.

选择排序的工作方式与Bubble排序相反，而Bubble排序会将所有最大值推到末尾，现在我们将最小值推到开始。

Every time it loops over the array it selects the smallest value, if it finds a lower value that then that becomes the new lowest value. When the loop is done it’ll take that minimum and put it on the front of the array before starting the loop again. This way the lowest value of each iteration is stacked onto the front until the whole array is sorted.

每次循环遍历数组时，它都会选择最小值，如果找到一个较低的值，那么它将变为新的最低值。 循环完成后，它将占用该最小值并将其放在数组的前面，然后再次开始循环。 这样，每次迭代的最低值都将堆积在前面，直到对整个数组进行排序。

Graphic/Animation thanks to

图形/动画得益于

const selection = arr => {  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];  arr.forEach((item, i) => {    let min = i;    for (let j = i + 1; j < arr.length; j++) {      if (arr[j] < arr[min]) min = j;    };    swap(arr, i, min);  });  return arr;};console.log(selection(unsortedArr));

插入排序 (Insertion Sort)

My personal favorite and the most performant of the three, insertion sort, is more similar to how you would sort something by hand.

我个人的最爱，也是这三个中性能最高的， 插入排序 ，与您手工排序的方式更相似。

We look at the array as two parts, the sorted and unsorted, with every time we find a new value we loop back to find its place in the sorted half. With each addition our sorted group grows until it is the whole array.

我们将数组分为两个部分，即已排序和未排序，每次找到新值时，我们都会循环返回以查找其在已排序一半中的位置。 每次添加后，我们的排序组就会增长，直到它成为整个数组为止。

Graphic/Animation thanks to

图形/动画得益于

const insertion = arr => {  arr.forEach((item, i) => {    let num = arr[i];    let j;    for (j = i - 1; j >= 0 && arr[j] > num; j--) {      arr[j + 1] = arr[j];    };    arr[j + 1] = num;  });  return arr;};console.log(insertion(unsortedArr));

比较方式 (Comparison)

One problem with using Big O Notation for comparing algorithms is that it’s based on the worse-case scenario, which may be the same across algorithms giving the false illusion that they’re equal. While Bubble, Selection, and Insertion sorts are all O(n^2), that doesn’t tell us much about the average or best case scenario or how they vary with the data structure.

使用Big O表示法比较算法的一个问题是，它基于最坏的情况，这在算法相同的情况下会给出错误的假想，即它们相等。 虽然冒泡，选择和插入排序均为O(n ^ 2)，但对于平均情况或最佳情况以及它们如何随数据结构变化，这并不能告诉我们太多。

Insertion sort wins every time. It also has the benefit of not needing to have the whole array before starting, which allows you to sort things in real-time as data comes in.

插入排序每次都会获胜。 它还具有不必在启动之前就拥有整个阵列的好处，这使您可以在数据输入时实时对事物进行排序。

Keep this in mind because you shouldn’t decide which algorithm is “best” before considering how your data is already organized.

请记住这一点，因为在考虑数据的组织方式之前，您不应该确定哪种算法是“最佳”的。

结论 (Conclusion)

These three are far from the best solutions to efficiently sorting large amounts of data, but they are some of the most intuitive to dip your toes into what can be an overwhelming ocean. 🌊

这三者并不是有效地对大量数据进行有效排序的最佳解决方案，但它们是将您的脚趾伸入一片巨大海洋的最直观的方法。 🌊

翻译自: