c++ - 排序和排序有什么区别？

Question

不，这不是课堂上的问题，我正在自己研究树和堆（部分排序的二叉树），我想知道如何正确定义与通用数据结构相关的这 2 个属性/操作。

score 28 · Accepted Answer

“排序”基本上是一组规则，用于确定哪些项目在其他项目之前或之后。IE：如果它们被排序，则相对顺序项目将出现。对于强制排序的集合，该排序通常根据比较运算符（特别是<）、接口（类似于 Java 的Comparable<T>）或比较回调和/或函数对象（如 C++ 的std::less）来指定。

还有一些集合被描述为“有序集合”。该词的用法略有不同，但含义相关。这意味着集合代表一系列项目，因此具有一些内置的顺序概念。（与哈希表相比。你在哈希表中添加一些东西，如果你遍历内容，你不知道它会出现在哪里。你知道，使用有序集合。）列表、向量、数组等是典型的有序集合。但是，对于非列表示例，PHP 的“数组”类型实际上是“有序映射”——保留键顺序的字典类型。键以它们第一次插入的顺序出现（或者你最后一次放置它们的顺序）ksort()或类似的）当你迭代数组时。
“排序”是根据给定顺序实际排列项目序列的过程。它通常只对有序集合完成......因为在没有“之前”概念的容器中将一个项目放在另一个之前没有多大意义，或者不会让您首先重新排列项目。（像集合和堆这样的结构也可以使用排序，并且添加和删除条目会根据排序改变底层树。有人可能会争辩说它们是逐位“排序”的。但是这个词通常用于表示一个操作立即重新排列。）

score 17 · Accepted Answer

非常粗略地说，排序指定了哪些元素应该在某个顺序中的哪些其他元素之前排序。排序是将这些元素的集合按排序指定的顺序排列的过程。

（有点令人困惑的是，也可以谈论“排序”一系列元素，这与将它们排序为由排序指定的某种顺序是同一回事。）

更新：

在实现方面，一个很好的例子是标准容器（例如地图，http ://en.cppreference.com/w/cpp/container/map ），它采用额外的模板参数来提供排序。这在地图的情况下默认为std::less<Key>。如果您想要自己的排序，则在创建地图时使用不同的比较器类型，然后使用它来代替。提供自己的比较器的一种常见方法是实现一个具有bool operator()(const Key& lhs, const Key& rhs) const.

score 14 · Accepted Answer

IBM 对有序集和有序集进行了区分：

集合可以排序或排序：
有序集合是一个集合，其元素按照添加到集合中的顺序排列。请注意，这是默认情况下创建集合的方式。例如：
{int} S1 = {3,2,5}; 
和
ordered {int} S1 = {3,2,5};
是等价的。
排序集是一个集合，其中元素按自然的升序（或降序）顺序排列。对于字符串，自然顺序是字典顺序。自然顺序还取决于系统区域设置。例如：
sorted {int} sortedS = {3,2,5};
和
ordered {int} orderedS = {2,3,5};
是等价的，并且迭代 sortedS 或 orderedS 将具有相同的行为。要指定降序，请添加关键字 reversed。

此外，国家信息保障合作伙伴于 2002 年向美国国家标准与技术研究院提出了对条款的解释：

问题：

术语“排序”和“排序”有什么区别？有时这些词可以互换使用。

陈述

尽管术语“排序”和“排序”有时在 IT 系统讨论中可以互换使用，但它们的含义有些不同。一个排序时，一个将项目分成不同的种类或类别；当一个人订购时，一个人以特定的顺序排列物品。

score 2 · Accepted Answer

有序集合意味着非易失性、可见和可重现的地址或元素相对于彼此的位置的概念。排序，然后，是一些任意标准的元素的实际放置。

score 2 · Accepted Answer

作为单词，它们几乎是计算机代码上下文中的同义词。例如：

SQL 有一个order by子句，因此您的数据行是有序的。
Java有一个SortedSetandSortedMap接口，一个接口的Collections.sort()方法List，一个Arrays.sort()数组的方法。

如果我要指定一个差异，那么我会说一个数组或java.util.List是有序的，但不是排序的。

当您将对象放入arrayorList时，它们会保留放入其中的顺序，您可以通过索引访问它们，但它们没有排序，因为顺序是任意的。

使用java.util.SortedSet，您可以按照您喜欢的任何顺序放入对象，因为它会按照java.util.Comparator 中natural ordering的公式或公式对它们进行排序。但是，您不能按索引访问元素。这将使它们排序但不排序。

score 1 · Accepted Answer

我认为用术语或排序算法来考虑这一点会有所帮助。一些排序算法保留顺序，而另一些则不保留。例如，考虑冒泡排序和选择排序这两种简单且低效的排序算法。冒泡排序保证保留顺序，而选择排序则不然。保留订单意味着相同的元素不会被交换。

保持顺序很重要，尤其是当项目包含未排序的其他数据时。例如，如果您对人的年龄进行排序，他们可能年龄相同但姓名不同，您可能希望保留原始顺序。

请参阅 wiki 上的排序算法，它们给出了时间复杂度和稳定性。稳定意味着保留原始顺序。
https://en.wikipedia.org/wiki/Sorting_algorithm

score 1 · Accepted Answer

排序：对集合的部分确定排列进行比较；碰撞是可能的

rank1 = max({foo1.bar, foo2.bar})
rank2 = min({foo2.kite, foo2.kite})

排序：加权排序的组合，允许集合完全且唯一地排列，没有潜在冲突；当单独的显式排序不足以满足子集时，插入顺序通常是一种后备解决方案

order = {
   ordering1 = (foo1.bar != foo2.bar) ? rank1(foo1, foo2) : ordering2(foo1, foo2)
   ordering2 = (foo1.kite != foo2.kite) ? rank2(foo1, foo2) : fallback(foo1, foo2)
}

排序：使用特定的访问和分区策略按顺序排列集合

 sort1 = strand(foo, order)
 sort2 = bubble(foo, order)

排序：按照顺序排列的集合的二进制状态（真或假）

is_sorted = {
  for (each foo)
    (is_ordered(foo(n), foo(n-1)) ? continue : return false;
  return true;
}

score 1 · Accepted Answer

顺序关系是可传递的。排序关系不是。
您可以订购一个整数序列。您只能对包含香蕉、苹果、浆果的集合进行排序...

score 1 · Accepted Answer

我对此进行了尝试...订购是用户定义的。例如，您可以根据最常访问、最流行等排序一组字符串。“一般”排序来自一组现有的操作系统方法。示例包括根据字符串区域设置按字母顺序对一组字符串进行排序。

我看到的方式如下。如果我订购一个集合，我正在指定一个谓词，该谓词确定一个项目将存在于集合中的哪个位置。如果我对集合进行排序，我通常会这样做，因为我想要快速查找。排序通常会导致从集合中快速查找给定项目的时间。这适用于字符串、整数等。

看看我的回答，我认为排序和排序几乎可以互换。但是，我仍然会说排序是用户定义的，排序是一个已知的概念。例如，我们都知道对名称列表进行排序会导致按字母顺序排序。如果我想通过我自己的算法对名称列表进行排序，比如根据受欢迎程度，我会介绍我自己的排序算法，它可以根据我认为合适的方式对字符串进行排序。因此，我会说，如果您引入一种排序算法，但根据您自己的要求对排序进行排序，那么您就是在排序。

c++ - 排序和排序有什么区别？

9 回答 9

Related

Reference