排序顺序，但在另一个订单排序某些特定元素

Question

假设我想排序按字母顺序排列的名称序列，但有一个附加规则：

Mike Cathy James Albert Austin：

如果在以下列表中的任何名称

出现，它们将被移动到序列的头部并且被排序为Mike -> Cathy -> James -> Albert -> Austin。

例如，如果原来的顺序是这样的：

Conan,Cary,Clarence,Cathy,Mike,Blake,Baron,Vaughan,Albert,Gabriel,Cathy 

期望的结果是：

迈克，凯蒂，凯蒂，阿尔伯特，男爵，布雷克，卡里，克拉伦斯，柯南，Gabriel，Vaughan

注意Mike, Cathy and Albert不再按字母顺序排序，它们作为一个整体位于其他常用名称的前面并具有其自己的预定义顺序。

---

而对于我的问题的一些进一步的解释：

1. 原始序列以非平凡的方式检索（例如，从一个数据库中），所以优选的是在一个检索整个序列时间并将其排序在内存中。
2. 不能保证这些特定名称中有多少出现在原始序列中，也不能保证它们出现多少次。

谁能告诉我如何以快速/有效的方式实现这一点？

Answer 1

一种方法：

1. 拆分名称的列表（或根据您的语言筛选）根据特殊分拣桶中的成员资格分为两个列表;
2. 根据您想要的顺序排列特殊名称列表;
3. 按字典顺序排列第二个列表;
4. 合并列表。

该方法应该适用于任何具有排序和列表或数组的名称以保存名称的语言。

在Python：

names=['Conan', 'Cary', 'Clarence', 'Cathy', 'Mike', 'Blake', 'Baron', 'Vaughan', 'Albert', 'Gabriel', 'Cathy'] 

specials=['Mike', 'Cathy', 'James', 'Albert', 'Austin'] 
# split the lists. 
n1=[n for n in names if n in specials] # ifilter would also work in Python 
n2=[n for n in names if n not in specials] 

# sort the first list based on order of specials, second lexicographically and combine: 
print sorted(n1, key=lambda n:specials.index(n))+sorted(n2) 

打印：

['Mike', 'Cathy', 'Cathy', 'Albert', 'Baron', 'Blake', 'Cary', 'Clarence', 'Conan', 'Gabriel', 'Vaughan'] 

---

一个改进是：

1. 创建包括否定整数的用于索引的两个元件的数据元素作为第一个元素放入特殊列表/数组中和第二个元素的名字;
2. 根据基于该元素的键或自定义cmp函数对列表/数组进行排序。

在Python中，您将在关键函数中使用元组。在C中，你会编写一个自定义的cmp函数。有了这个，您可以根据您的语言特点对names进行排序。

元组中的两个元素将是特殊名称中的名称的否定索引（针对基于零的索引进行调整），然后是名称。如果非零，元组的第一个元素将胜出第二个元素。由于第一个元素是整数，因此即使specials中有超过10个名称，它也会正确排序。

同样，在Python：

def cf(n): 
    rtr=(specials.index(n)-len(specials)-1 if n in specials else 0, n) 
    print rtr # to show what is being generated for the sort key... 
    return rtr 

names.sort(key=cf) # sorts inplace 

打印：

(0, 'Conan') 
(0, 'Cary') 
(0, 'Clarence') 
(-5, 'Cathy') 
(-6, 'Mike') 
(0, 'Blake') 
(0, 'Baron') 
(0, 'Vaughan') 
(-3, 'Albert') 
(0, 'Gabriel') 
(-5, 'Cathy') 

现在names已经整理就地和一个通到：

['Mike', 'Cathy', 'Cathy', 'Albert', 'Baron', 'Blake', 'Cary', 'Clarence', 'Conan', 'Gabriel', 'Vaughan'] 

Answer 2

所以我的算法是伪代码中的以下内容。

输入：字符串矢量V，字符串（在特殊情况下）的一个清单当然L，相关联的至L

订单

Let pivot be a random element of V 
Let A,B,C be three empty arrays of strings 
For name in V 
    if (name in L) 
     add name to A 
    else if (name <= pivot) // for the lexicographic order 
     add name to B 
    else if (name > pivot) // for the lexicographic order 
     add name to C 
If (pivot in L) 
    add pivot to A 
Else 
    add pivot to B 
Sort A for the order associated with L 
Sort B for the lexicographic order 
Sort C for the lexicographic order 
Merge B in A 
Merge C in A 
Return A 

Answer 3

一招，几乎任何对特殊情况进行排序很简单，就是将你的元素转换成按键，这样就可以按你想要的方式排序，定期进行排序，然后将它们转换回来。

例如，

1. 转到普通的名字，如 “加布里埃尔” 到 “1.Gabriel”
2. 打开特殊的名字，像 “凯西” 到 “0.1.Cathy” 和 “迈克” 到​​“0.0。麦克风”。
3. 正常排序。前导零将在常规名称之前强制使用特殊名称。在特殊名称中，下一位数字将给出所需的排序顺序。在常规名称中，排序将按字典顺序排列。
4. 撤消转换。由于原始转换只是添加了信息，因此您总是可以转换回来。

某些语言或库（如C或C++）可以覆盖比较。这仅对简单情况有用（且有效）。其他语言（比如Python）有一种方法可以根据需要提供排序键，这将使这种方法变得非常简单。

如果我记得，Knuth在TAoCP中有这种方法的一个例子。在那一本书中，他拥有书名，排序规则就像盲人一样，把'A'和'the'移到标题的末尾等等。