订购和排序有什么区别？

Question

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

Answer 1

• 的“订购”基本上是一组决定之前哪些项目来了，还是之后，还有什么其他项目的规则。 IE：如果他们被排序，则相对的订单商品会出现。对于强制执行排序的集合，通常通过比较运算符（特别是<），接口（Java的Comparable<T>）或比较回调函数和/或函数对象（如C++的std::less）来指定该排序。

  还有描述为“有序集合”的集合。这个词略有不同，但相关的含义。这意味着该集合代表序列项目，因此具有一些内置的订单概念。 （与哈希表相反，你在哈希表中添加了一些东西，如果你重复遍历内容，你不知道它会出现在哪里。有了一个有序集合，你就知道了。）列表，向量，数组等是典型的有序集合。不过，对于非列表示例，PHP的“数组”类型实际上是一个“有序地图” - 一种保留键顺序的字典类型。当你迭代数组时，键以它们首次插入的顺序出现（或者你最后放置的顺序为ksort()等）。

• “排序”是按照给定顺序实际安排一系列项目的过程。它通常只在有序集合上完成......因为在一个没有“之前”概念的容器中将一个项目放在另一个项目之前没有太大意义，或者不会让您首先重新排列项目。 （像集合和堆结构也可以使用排序，并且添加和移除条目会根据排序改变底层树，但人们可能会说他们正在逐步“排序”，但这个词通常用来表示一个操作，是否一次重新整理。）

Answer 2

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

（稍微容易混淆，它也可以谈“排序”元素的序列，这意味着同样的事情，他们整理成一个订购指定的一些顺序）

---

UPDATE：

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

Answer 3

IBM makes a distinction between sorted and ordered sets：

集既可以的进行排序：

• 的有序集合是一组其元素被布置在它们被添加到订单集合。请注意，这是默认情况下创建集的方式。例如：

  {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将具有相同的行为。 要指定降序，请添加关键字reverse。

此外，国家信息安全保障合作proposed an interpretation of the terms到美国国家标准与技术研究所于2002年：

问题：

什么是“排序”的条款之间的区别和“订购”？ 有时这些词可以互换使用。

声明

虽然术语“分拣”和“订购”有时 互换在IT系统的讨论，他们有有所不同 含义。当分类时，将项目分为不同的种类或 类;当一个订单，一个安排在一个特定的 订单项目。

Answer 4

我认为这有助于在条款或排序算法中想到这一点。一些排序算法保留顺序，而其他排序算法则不排序例如，考虑两种天真和低效的排序算法冒泡排序和选择排序。泡泡排序是保证顺序和选择排序不是。保留订单意味着相同的元素不会被交换。

保留顺序非常重要，尤其是当项目包含未被排序的其他数据时。例如，如果您按年龄分类，他们可能年龄相同，但名称不同，您可能想要保留原始订单。

查看wiki中的排序算法，他们给出了时间复杂度和稳定性。稳定意味着原始订单被保留。
https://en.wikipedia.org/wiki/Sorting_algorithm

Answer 5

排名：一个集合的部分确定性排列的比较;碰撞是可能的

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) 

排序的顺序来的一组安排：按照订单（true或false）排列集合的二进制状态

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

Answer 6

订单关系是可传递的。排序关系不是。
您可以订购一系列整数。你只能排序一组包含香蕉，苹果，浆果...

Answer 7

我刺这... 订购是用户定义的。例如，您可以根据访问量最大，流行度最高的字符串来命令一组字符串。“一般”排序来自一组现有的操作系​​统方法。示例包括基于字符串区域设置按字母顺序对一组字符串进行排序。

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

看着我的回答，我认为订购和分拣几乎是可以互换的。但是，我仍然会说排序是用户定义的，排序是一个已知的概念。例如，我们都知道排序名称列表会导致按字母顺序排序。如果我想通过我自己的算法对名称列表进行排序，请根据流行度来说，我会介绍自己的排序算法，按照我认为合适的顺序排序字符串。所以，我想说如果你引入一个算法来排序，但是按照你自己的要求排序，那么你就是在排序。

Answer 8

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

Answer 9

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

• SQL有一个order by子句，所以您的数据行是有序的。
• Java有一个SortedSet和SortedMap接口，用于List接口Collections.sort()方法，以及用于阵列的Arrays.sort()方法。

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

当你把对象转换成array或List，他们保留它们被摆在那里的顺序，你可以通过索引来访问他们，但他们不排序，因为顺序是任意。

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