在遗传算法中出现等式约束

by Onel Harrison

通过Onel Harrison

排序算法中的稳定性-等式的处理 (Stability in Sorting Algorithms — A Treatment of Equality)

Algorithms are at the heart of computer science. Algorithms used for sorting are some of the most fundamental, useful, and consequently, ubiquitous.

算法是计算机科学的核心。 用于排序的算法是一些最基本，最有用且因此无所不在的算法。

Algorithm — a finite set of unambiguous steps for solving a specific problem.

算法-解决特定问题的有限的明确步骤集。

We constantly and often unconsciously sort and rely on the order of grouped objects. For instance, we rank tasks on a list according to priority. We stack books on shelves by their height. We sort rows in a spreadsheet or database, or rely on the alphabetical order of words in a dictionary. Sometimes, we even perceive a certain kind of beauty in ordered arrangements.

我们经常不知不觉地对分组对象的顺序进行排序和依赖。 例如，我们根据优先级在列表上对任务进行排名。 我们按书架的高度将书堆起来。 我们对电子表格或数据库中的行进行排序，或者依赖字典中单词的字母顺序。 有时，我们甚至有秩序地安排一种美感。

As programmers, knowing how we sort is important because it affects what a sorted arrangement might look like. Not all sorts order objects in the same way! Because of this, the results of sorting operations differ based on the algorithms used. If this goes unacknowledged, we might surprise ourselves or the people who use our software.

作为程序员，知道我们是如何排序是非常重要的，因为它影响的有序排列可能是什么样子。 并非所有对象都以相同的方式排序！ 因此，根据所使用的算法，排序操作的结果会有所不同。 如果不了解这一点，我们可能会让自己或使用我们软件的人员感到惊讶。

The stability of sorting algorithms is one of the distinguishing properties among them. It deals with how the algorithm treats comparable items with equal sort keys.

排序算法的稳定性是它们之间的区别属性之一。 它处理算法如何使用相等的排序键来处理可比较的项目。

Sort key — A key used to determine the ordering of items in a collection, e.g. age, height, position in the alphabet, etc.

排序键-用于确定集合中项目顺序的键，例如年龄，身高，字母位置等。

A stable sorting algorithm maintains the relative order of the items with equal sort keys. An unstable sorting algorithm does not. In other words, when a collection is sorted with a stable sorting algorithm, items with the same sort keys preserve their order after the collection is sorted.

稳定的排序算法使用相同的排序关键字维护项目的相对顺序。 不稳定的排序算法则不会。 换句话说，当使用稳定的排序算法对集合进行排序时，具有相同排序键的项目将在对集合进行排序后保留其顺序。

示例，代码和演示 (An Example, Code, and a Demo)

The image above illustrates the effect of a stable sort. On the left, the data was sorted alphabetically by Name. After sorting the data by Grade, you can see that the alphabetical order of the names was maintained for each row with the same Grade.

上图显示了稳定排序的效果。 在左侧，数据按名称按字母顺序排序。 在按等级对数据进行排序之后，您可以看到为具有相同等级的每一行维护了名称的字母顺序。

With an unstable sort, there is no guarantee the alphabetical ordering is maintained as shown in the image above.

对于不稳定的排序，不能保证如上图所示保持字母顺序。

您并不总是需要稳定的排序 (You don’t always need a stable sort)

Knowing whether or not the sort you use is stable is particularly important. Especially in situations when your data already has some order to it that you would like to maintain when you sort it by another sort key. For example, you have rows in a spreadsheet containing student data that is, by default, sorted by name. You would like also to sort it by grades while maintaining the sorted order of the names.

知道您使用的排序是否稳定尤其重要。 尤其是在您的数据已经具有某种顺序的情况下，当您使用另一个排序键对数据进行排序时，尤其要注意这种情况。 例如，您在电子表格中有一些行，其中包含默认情况下按名称排序的学生数据。 您还希望按等级对它进行排序，同时保持名称的排序顺序。

On the other hand, the stability of the sort doesn’t matter when the sort keys of the objects in a collection are the objects themselves — an array of integers or strings, for example — because we can’t tell the difference among the duplicated keys.

另一方面，当集合中对象的排序键是对象本身(例如整数或字符串数​​组)时，排序的稳定性并不重要，因为我们无法区分重复项之间的区别键。

// JavaScript

// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.

var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]

// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.

var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

杂物无所不在-了解您的杂物 (Sorts are everywhere — know your sorts)

It’s quite easy to find out if the default sort in your programming language or library is stable. The documentation should include this information. For instance, default sorting is stable in Python, unstable in Ruby, and undefined? in JavaScript (it depends on the browser’s implementation).

找出编程语言或库中的默认排序是否稳定是很容易的。 该文档应包含此信息。 例如， 默认排序在Python中是稳定的 ， 在Ruby中 是 不稳定的 ，并且未定义 ？ JavaScript (取决于浏览器的实现)。

Here are a few common sorting algorithms and their stability:

以下是一些常见的排序算法及其稳定性：

• Insertion Sort — Stable
  插入排序-稳定
• Selection Sort — Unstable
  选择排序-不稳定
• Bubble Sort — Stable
  气泡排序-稳定
• Merge Sort — Stable
  合并排序-稳定
• Shell Sort — Unstable
  外壳排序-不稳定
• Timsort — Stable
  Timsort —稳定

See Wikipedia for a more exhaustive list.

有关更详尽的列表，请参见Wikipedia 。

现在是演示时间？ (It’s demo time ?‍?)

This demo shows the effect of using a stable (insertion sort) and unstable sorting (selection sort) algorithm to sort a small table of data. I had a bit of fun and practically reverse engineered React while building this. Have a look at the source.

该演示演示了使用稳定(插入排序)和不稳定排序(选择排序)算法对小的数据表进行排序的效果。 在构建此代码时，我有一些乐趣，并且实际上是反向工程的React。 看一下来源 。

下一步是什么？ (What’s next?)

If you are thirsty for more knowledge about the stability of other sorting algorithms, Wikipedia has a good comparison table and additional information on well known sorting algorithms.

如果您想了解有关其他排序算法稳定性的更多知识，那么Wikipedia可以提供一个很好的比较表以及有关众所周知的排序算法的其他信息。

Until next time, peace.

直到下一次，和平。

学习了新知识还是喜欢阅读本文？ 拍打它，分享它，以便其他人也可以阅读，然后继续阅读。 也可以发表评论。 (Learned something new or enjoyed reading this article? Clap it up ?, share it so that others can read too, and follow along for more. Feel free to leave a comment too.)

翻译自: https://www.freecodecamp.org/news/stability-in-sorting-algorithms-a-treatment-of-equality-fa3140a5a539/

在遗传算法中出现等式约束