排序规则的优先顺序
 
 
排序规则的优先顺序（也称为排序规则类型强制规则）是赋予一组规则的术语，而这组规则决定： 
 
取值为字符串的表达式的最终结果的排序规则。

 
区分排序规则的运算符所使用的排序规则，这些运算符使用字符串输入但不返回字符串，如 LIKE 和 IN。 
 
 
排序规则的优先顺序规则只适用于字符串数据类型：char、varchar、text、nchar、nvarchar 和 ntext。具有其它数据类型的对象不参加排序规则的评估。
 
 
所有对象的排序规则可归为四类中的一种。每类的名称叫做排序规则标志。
 
 
排序规则标志
对象类型
强制默认
任何 Transact-SQL 字符串变量、参数、字面值、目录内置函数的输出、或不使用字符串输入但产生字符串输出的内置函数。 
如果在用户定义函数、存储过程或触发器中声明某个对象，则将该对象指派为在其中创建函数、存储过程或触发器的数据库的默认排序规则。如果在批处理中声明该对象，则将其指派为连接所使用的当前数据库的默认排序规则。
隐性 X
列引用。从为表或视图中的列定义的排序规则得到表达式（由 X 表示）的排序规则。 
即使 CREATE TABLE 或 CREATE VIEW 语句中的 COLLATE 子句给列显式指派了排序规则，该列引用仍归为隐性。
显式 X
使用表达式中的 COLLATE 子句显式投影到特定排序规则（由 X 表示）的表达式。
无排序规则
表示表达式的值是两个字符串之间操作的结果，而这两个字符串具有隐性排序规则标志的冲突排序规则。表达式的结果被定义为不具有排序规则。
 
 
 
只引用一个字符串对象的简单表达式的排序规则标志是被引用对象的排序规则标志。
 
 
如果复杂表达式所引用的两个操作数表达式的排序规则标志相同，则该复杂表达式的排序规则标志为数表达式的排序规则标志。
 
 
如果复杂表达式所引用的两个操作数表达式的排序规则不同，则该复杂表达式最终结果的排序规则标志基于下列规则： 
 
显式优先于隐性。隐性优先于强制默认。换言之， 
显式 > 隐性 > 强制默认
 
组合两个已指派给不同排序规则的显式表达式将生成错误。 
显式 X + 显式 Y = 错误
 
组合两个具有不同排序规则的隐性表达式将产生无排序规则。 
隐性 X + 隐性 Y = 无排序规则
 
将无排序规则的表达式与任何标志的表达式组合，除了显式排序规则外（参见下一项），都产生无排序规则标志的结果。 
无排序规则 + 任何标志 = 无排序规则
 
将无排序规则的表达式与显式排序规则的表达式组合将产生具有显式标志的表达式。 
无排序规则 + 显式 X = 显式
 
 
下面的示例说明上述规则。
 
USE tempdb
GO

CREATE TABLE TestTab (
   id int, 
   GreekCol nvarchar(10) collate greek_ci_as, 
   LatinCol nvarchar(10) collate latin1_general_cs_as
   )
INSERT TestTab VALUES (1, N'A', N'a')
GO
 
 
下面查询中的谓词具有排序规则冲突，因此产生错误：
 
SELECT * 
FROM TestTab 
WHERE GreekCol = LatinCol
 
 
下面是结果集。
 
Msg 446, Level 16, State 9, Server CTSSERV, Line 1
Cannot resolve collation conflict for equal to operation.
 
 
下面查询中的谓词在排序规则 greek_ci_as 中取值，因为右边表达式具有显式标志，优先于右边表达式的隐性标志：
 
SELECT * 
FROM TestTab 
WHERE GreekCol = LatinCol COLLATE greek_ci_as
 
 
下面是结果集。
 
id          GreekCol             LatinCol
 ----------- -------------------- --------------------
           1 a                    A

(1 row affected)
 
 
下面查询中的 case 表达式没有排序规则标志，所以不能出现在选择列表中，也不能由区分排序规则的运算符操作。不过，这些表达式可由不区分排序规则的运算符操作。
 
SELECT (CASE WHEN id > 10 THEN GreekCol ELSE LatinCol END) 
FROM TestTab
 
 
下面是结果集。
 
Msg 451, Level 16, State 1, Line 1
Cannot resolve collation conflict for column 1 in SELECT statement.

SELECT PATINDEX((CASE WHEN id > 10 THEN GreekCol ELSE LatinCol END), 'a')
FROM TestTab
 
 
下面是结果集。
 
Msg 446, Level 16, State 9, Server LEIH2, Line 1
Cannot resolve collation conflict for patindex operation.

SELECT (CASE WHEN id > 10 THEN GreekCol ELSE LatinCol END) COLLATE Latin1_General_CI_AS 
FROM TestTab
 
 
下面是结果集。
 
--------------------
a

(1 row affected)
 
 
下表汇总了上述规则。
 
 
操作数强制标志

显式 X

隐性 X
强制默认

无排序规则
显式 Y
生成错误
结果为显式 Y
结果为显式 Y
结果为显式 Y
隐性 Y
结果为显式 X
结果为无排序规则
结果为隐性 Y
结果为无排序规则
强制默认
结果为显式 X
结果为隐性 X
结果为强制默认
结果为无排序规则
无排序规则
结果为显式 X
结果为无排序规则
结果为无排序规则
结果为无排序规则
 
 
 
运算符和函数区分排序规则或不区分排序规则： 
 
区分排序规则表示指定无排序规则操作数是编译时错误。表达式结果不能是无排序规则。

 
不区分排序规则表示操作数和结果可以是无排序规则。 
 
 
比较运算符以及 MAX、MIN、BETWEEN、LIKE 和 IN 运算符都区分排序规则。运算符所使用的字符串被赋以具有较高优先顺序的操作数的排序规则标志。UNION 运算符也区分排序规则，且所有的字符串操作数和最终结果被赋以具有最高优先顺序的操作数的排序规则。按列评估 UNION 操作数和结果的排序规则优先顺序。
 
 
赋值运算符不区分排序规则，右边的表达式投影到左边的排序规则上。
 
 
字符串串联运算符不区分排序规则，两个字符串操作数和结果被赋以具有最高排序规则优先顺序的操作数的排序规则标志。UNION ALL 和 CASE 运算符不区分排序规则，所有的字符串操作数和最终结果都被赋以具有最高优先顺序的操作数的排序规则标志。按列评估 UNION ALL 操作数和结果的排序规则优先顺序。
 
 
CAST、CONVERT 和 COLLATE 函数区分 char、varchar 和 text 数据类型的排序规则。如果 CAST 和 CONVERT 函数的输入和输出是字符串，则输出字符串具有输入字符串的排序规则标志。如果输入不是字符串，则输出字符串为强制默认并被赋以连接所使用的当前数据库的排序规则，或是包含引用 CAST 或 CONVERT 的用户定义函数、存储过程或触发器的数据库的排序规则。
 
 
对于返回字符串但不使用字符串输入的内置函数，结果字符串为强制默认并被赋以当前数据库的排序规则，或是包含引用该函数的用户定义函数、存储过程或触发器的数据库的排序规则。
 
 
下列函数区分排序规则，其输出字符串具有输入字符串的排序规则标志： 
 
CHARINDEX

 
DIFFERENCE

 
ISNUMERIC

 
LEFT

 
LEN

 
LOWER

 
PATINDEX

 
REPLACE

 
REVERSE

 
RIGHT

 
SOUNDEX

 
STUFF

 
SUBSTRING

 
UPPER 
 
 
下列附加规则也适用于排序规则优先顺序： 
 
在已经是显式表达式的表达式上不能有多个 COLLATE 子句。例如，下面的 WHERE 子句是不合法的，因为将 COLLATE 子句指定给的表达式已经是显式表达式： 
WHERE ColumnA = ( 'abc' COLLATE French_CI_AS) COLLATE French_CS_AS
 
text 数据类型不允许代码页转换。如果排序规则的代码页不同，不能将文本表达式从一种排序规则投影到另一种排序规则。如果右边文本操作数的排序规则代码页与左边文本操作数不同，则赋值运算符不能赋值。 
 
 
在数据类型转换后确定排序规则的优先顺序。产生结果排序规则的操作数可以与提供最终结果数据类型的操作数不同。例如，考察下面的批处理：
 
CREATE TABLE TestTab
   (PrimaryKey int PRIMARY KEY,
    CharCol char(10) COLLATE French_CI_AS
   )

SELECT *
FROM TestTab
WHERE CharCol LIKE N'abc'
 
 
简单表达式 N'abc' 的 Unicode 数据类型具有较高的数据类型优先顺序，所以结果表达式将 Unicode 数据类型指派给 N'abc'。然而，表达式 CharCol 具有隐性排序规则标志，而 N'abc' 具有较低的强制默认排序规则标志，所以使用的排序规则是 CharCol 的 French_CI_AS 排序规则。

问题
 
在项目中 我们经常需要将一个有父子关系的列表按照树的深度优先遍历的方式排序。所以写了一个通用的排序算法。
 
源码
 
github 地址： CollectionsOpt.java。更多分享参见 https://ndxt.github.io。 
 
 public interface ParentChild<T> {
        boolean parentAndChild(T p, T c);
    }

public static <T> void sortAsTree(List<T> list, ParentChild<? super T> c) {
        int n=list.size();
        if(n<2)
            return ;
        //sorted 已经排序好的数量
        int sortedInd = 0;
        int [] parentInds = new int [n];
        while(sortedInd < n-1 ){
            // 找到所有的根节点
            int parentInd = -1;
            for(int i= sortedInd;i<n;i++){
                boolean isParent = true;
                for(int j=sortedInd;j<n;j++){
                    if(i != j && c.parentAndChild(list.get(j),list.get(i))){
                        isParent = false;
                        break;
                    }
                }
                if(isParent){
                    parentInd = i;
                    break;
                }
            }
            if(parentInd == -1)
                break;

            moveListItem(list,parentInd,sortedInd);
            parentInds[0]=sortedInd;
            sortedInd ++;
            int pathDeep=1;
            while(pathDeep>0){
                int newInsert = 0;
                for(int i=sortedInd;i<n;i++){
                    if(c.parentAndChild(list.get(parentInds[pathDeep-1]),list.get(i))){
                        moveListItem(list,i,sortedInd);
                        parentInds[pathDeep]=sortedInd;
                        pathDeep ++;
                        sortedInd ++;
                        newInsert ++;
                    }
                }
                if(newInsert==0){
                    pathDeep--;
                }
            }
            // 查找根节点的所有子元素
            //sortedInd = sortAsTreePiece(list,c,sortedInd);
        }
    }
 
测试
 

    public static void main(String[] args) {
        List<Integer> nodeList = new ArrayList<Integer>();
        nodeList.add(223);
        nodeList.add(222);
        nodeList.add(221);
        nodeList.add(22);
        nodeList.add(123);
        nodeList.add(121);
        nodeList.add(11);
        nodeList.add(12);
        nodeList.add(21);
        nodeList.add(2);
        nodeList.add(1);

        CollectionsOpt.sortAsTree(nodeList,(p,c)-> p == c / 10);
        System.out.println(nodeList);
    }
 
结果
 

Java中HashMap是一种用于存储“键”和“值”信息对的数据结构。不同于Array、ArrayList和LinkedLists，它不会维持插入元素的顺序。因此对HashMap排序的掌握很重要。HashMap排序有两个步骤：
一.通过map.entrySet()方法获取键值对;并将键值对传递给链表list；

二.自定义比较器来使用Collections.sort()方法排序链表。

Collections.sort(list, new Comparator<Entry<String,Integer>>() { 
 
            public int compare(Entry<String, Integer> ele1, 
 
                    Entry<String, Integer> ele2) { 
 
                return ele1.getValue().compareTo(ele2.getValue()); 
 
            } 
 
        }); 


下面来看看具体实例来演示如何排序Value：
题一：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
例如，
给定数组 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。
注意：
你可以假设给定的 k 总是合理的，1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
运用以上方法解答：
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> list = new ArrayList<Integer>();
        Map<Integer,Integer>intMap = new HashMap<Integer,Integer>();
        for(int i:nums){
            if(intMap.get(i) == null){
                intMap.put(i,1);
            }
            else{
                int t = intMap.get(i)+1;
                intMap.put(i,t);
            }
        }
        List<Map.Entry<Integer,Integer>>li = new LinkedList<Map.Entry<Integer,Integer>>();
        li.addAll(intMap.entrySet());
        Collections.sort(li,new Comparator<Map.Entry<Integer,Integer>>(){
            public int compare(Map.Entry<Integer,Integer>e1,Map.Entry<Integer,Integer>e2){
                return e2.getValue().compareTo(e1.getValue()); 
            }
        });
        int tem = 0;
        for(Iterator <Map.Entry<Integer,Integer>>it = li.iterator(); it.hasNext();){
            list.add(it.next().getKey());
            tem++;
            if(tem ==k){break;}
            
        }
        return list;
    }
}
以上题目再复杂一点有：

给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
示例 1：
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。
示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。
注意：
假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。
该题比第一题要多考虑value值相同时对键KEY进行排序。
同样用以上方法变通一下解答：
import java.util.Map.Entry;
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> result = new ArrayList<>();
        Map<String,Integer> map = new HashMap<String,Integer>();
        
        for(String a:words){
            String b = a;
            if(map.get(b)==null){map.put(b,1);}
            else{
                int c = map.get(b) + 1;
                map.put(b,c);
            }
        }
        //Set<Entry<String,Integer>> entry = map.entrySet();
        List<Entry<String,Integer>> list = new ArrayList<>();
        list.addAll(map.entrySet());
        Collections.sort(list,new Comparator<Map.Entry<String,Integer>>(){
            public int compare(Map.Entry<String,Integer>e1,Map.Entry<String,Integer>e2){
                int re = e2.getValue().compareTo(e1.getValue());
                if(re!=0){return re;}
                else{return e1.getKey().compareTo(e2.getKey());}
            }
        });
        for(int i=0;i<k;i++){
            result.add(list.get(i).getKey());
        }
        return result;
    }
}


个人总结：灵活使用Comparator接口可以实现HashMap的灵活排序：包括分别对键、值的升降序排序，优先按值、其次按键排序，或者优先按键、其次按值排序；以上实现只需重写compare方法。
1.对值value降序排序：

 public int compare(Map.Entry<Integer,Integer>e1,Map.Entry<Integer,Integer>e2){
                return e2.getValue().compareTo(e1.getValue()); 
            }
2.对值value升序排序：

 public int compare(Map.Entry<Integer,Integer>e1,Map.Entry<Integer,Integer>e2){
                return e1.getValue().compareTo(e2.getValue()); 
            }
3.对键KEY降序排列：

 public int compare(Map.Entry<Integer,Integer>e1,Map.Entry<Integer,Integer>e2){
                return e2.getKey().compareTo(e1.getKey()); 
            }
4.对键KEY升序排列：

 public int compare(Map.Entry<Integer,Integer>e1,Map.Entry<Integer,Integer>e2){
                return e1.getKey().compareTo(e2.getKey()); 
            }
5.优先按值value降序、其次按键key升序排序：

public int compare(Map.Entry<String,Integer>e1,Map.Entry<String,Integer>e2){
                int re = e2.getValue().compareTo(e1.getValue());
                if(re!=0){return re;}
                else{return e1.getKey().compareTo(e2.getKey());}
            }
6.优先按键key降序、其次按值value升序排序：

public int compare(Map.Entry<String,Integer>e1,Map.Entry<String,Integer>e2){
                int re = e2.getKey().compareTo(e1.getKey());
                if(re!=0){return re;}
                else{return e1.getValue().compareTo(e2.getValue());}
            }
如此类推...

行优先机制的编译器，比如C/C++，CUDA，python等，意思为优先保留第1行的所有元素，以此类推。
列优先机制的编译器，比如Fortune, Matlab等，意思为优先保留第1列的所有元素，以此类推。
如何应用？
就是内层循环尽量用连续的数据。
比如行优先的编译器，a(i,j)，循环的时候内层为列，外层为行，寻址速度更快，因为数据连续。
而列优先的编译器，内层仍然为列的话，寻址是错开的，会带来额外的时间开销。


另外matlab默认行矩阵。


一个简单的matlab测试案例如下：
function test_for_cycle()
    data = ones(1000, 30, 4);
    sum =0;
    tic;
    for i=1:size(data,1)
        for j=1:size(data,2)
            for k=1:size(data,3)
                sum = sum+data(i,j,k);
            end
        end
    end
    toc;
    sum =0;
    tic;
    for k=1:size(data,3)
        for j=1:size(data,2)
            for i=1:size(data,1)
                sum=sum+data(i,j,k);
            end
        end
    end
    toc;
end 
测试结果如下：


由此可得，在Matlab的循环运算里，尽量把A（i,j,k）的i放在内圈，运算效率差10倍；而C语言则相反，把k放在内圈加速运行。