当前位置：首页 > 编程日记 > 正文

在遗传算法中出现等式约束_排序算法中的稳定性-等式的处理

编程日记 2024-08-07 13:10:00

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

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.

直到下一次，和平。

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

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

https://www.dkcj.cn/info/13219.html

在遗传算法中出现等式约束_排序算法中的稳定性-等式的处理

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

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

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

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

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

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

相关文章：

vconsole 调试查看LOG VUE在手机上调试手机查看h5的日志

无参数的lambda匿名函数

scrum项目管理_Scrum，用于初创企业（或针对该项目的任何项目）

升级Jekyll 3.0

jquery学习（3）--高级选择器

h5 返回上一页并且刷新页面

kotlin中的异常处理_如何使用assertFailsWith在Kotlin中测试异常

学习dubbo框架的问题

Android 控件之 Menu 菜单

VUE保存页面的数据，VUE页面显示就执行某个函数，VUE页面隐藏就执行某个函数

npm i和npm_让您的NPM套件包含Jest和Codecov☂️

分页传页数的方法

VUE input唤起键盘底部固定的标签被顶上去解决办法

unity中摄像机的控制---调整摄像机，不让他摔倒

java正则表达式课程_通过此免费课程学习正则表达式

Codeforces Round #370 (Div. 2)

pat1004. Counting Leaves (30)

css 引用字体

系统技术方案系统构架_构架系统时应注意的事项

[LeetCode] Add Digits

vue 点击事件执行多次

如何以及为什么使用Android Visibility Listeners

在vue中使用Element-UI

Flex布局教程（来源：阮一峰）

ibatis的there is no statement named xxx in this SqlMap

javascript案例_如何在JavaScript中使用增强现实-一个案例研究

久未更 ~ 一之 —— 关于ToolBar

SQLServer怎样把本地数据导入到远程服务器上(转载)

input 默认样式的修改

巨石加密_点餐：如何吃一个可怕的巨石