如何在 C# 中对顺序 GUID 进行排序？

Question

顺序 GUID 是唯一的，但是是按顺序创建的；该顺序略有不同，与使用标准 .NET Guid 比较器时获得的顺序不同。

我正在寻找将按顺序 GUID 规则排序的 C# Guid 比较器。

==更新==

我特别指的是 SQL 服务器中由 NewSequentialId() 创建的顺序 GUID，尽管我现在意识到标准 Win32 API 调用 UuidCreateSequential() 使用不同的方案 SQL服务器（我写问题的时候以为他们是一样的）

== 更新 2==

petelids 使用例如List.Sort() 给出以下序列（使用 GUID 的初始列表，每个 4 位位置有一个 1）...

01000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000
00010000-0000-0000-0000-000000000000
00100000-0000-0000-0000-000000000000
00000100-0000-0000-0000-000000000000
00001000-0000-0000-0000-000000000000
00000001-0000-0000-0000-000000000000
00000010-0000-0000-0000-000000000000
00000000-0100-0000-0000-000000000000
00000000-1000-0000-0000-000000000000
00000000-0001-0000-0000-000000000000
00000000-0010-0000-0000-000000000000
00000000-0000-0100-0000-000000000000
00000000-0000-1000-0000-000000000000
00000000-0000-0001-0000-000000000000
00000000-0000-0010-0000-000000000000
00000000-0000-0000-0001-000000000000
00000000-0000-0000-0010-000000000000
00000000-0000-0000-0100-000000000000
00000000-0000-0000-1000-000000000000
00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
00000000-0000-0000-0000-000000000100
00000000-0000-0000-0000-000000001000
00000000-0000-0000-0000-000000010000
00000000-0000-0000-0000-000000100000
00000000-0000-0000-0000-000001000000
00000000-0000-0000-0000-000010000000
00000000-0000-0000-0000-000100000000
00000000-0000-0000-0000-001000000000
00000000-0000-0000-0000-010000000000
00000000-0000-0000-0000-100000000000

与 List.Sort()

返回的以下顺序相反

00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
00000000-0000-0000-0000-000000000100
00000000-0000-0000-0000-000000001000
00000000-0000-0000-0000-000000010000
00000000-0000-0000-0000-000000100000
00000000-0000-0000-0000-000001000000
00000000-0000-0000-0000-000010000000
00000000-0000-0000-0000-000100000000
00000000-0000-0000-0000-001000000000
00000000-0000-0000-0000-010000000000
00000000-0000-0000-0000-100000000000
00000000-0000-0000-0001-000000000000
00000000-0000-0000-0010-000000000000
00000000-0000-0000-0100-000000000000
00000000-0000-0000-1000-000000000000
00000000-0000-0001-0000-000000000000
00000000-0000-0010-0000-000000000000
00000000-0000-0100-0000-000000000000
00000000-0000-1000-0000-000000000000
00000000-0001-0000-0000-000000000000
00000000-0010-0000-0000-000000000000
00000000-0100-0000-0000-000000000000
00000000-1000-0000-0000-000000000000
00000001-0000-0000-0000-000000000000
00000010-0000-0000-0000-000000000000
00000100-0000-0000-0000-000000000000
00001000-0000-0000-0000-000000000000
00010000-0000-0000-0000-000000000000
00100000-0000-0000-0000-000000000000
01000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000

Answer 1

Sql 服务器和 .NET 排序 guid 的方式不同。

.NET 框架中有一个名为 SqlGuid 的结构，其行为方式应与 Sql 服务器中的 guid 相同。

考虑以下改编自 here 的示例：

List<Guid> a = new List<Guid>();
a.Add(new Guid("3AAAAAAA-BBBB-CCCC-DDDD-2EEEEEEEEEEE"));
a.Add(new Guid("2AAAAAAA-BBBB-CCCC-DDDD-1EEEEEEEEEEE"));
a.Add(new Guid("1AAAAAAA-BBBB-CCCC-DDDD-3EEEEEEEEEEE"));
Console.WriteLine("--Unsorted Guids--");
foreach (Guid g in a)
{
    Console.WriteLine("{0}", g);
}
a.Sort();
Console.WriteLine("--Sorted Guids--");
foreach (Guid g in a)
{
    Console.WriteLine("{0}", g);
}

List<SqlGuid> b = new List<SqlGuid>();
b.Add(new SqlGuid("3AAAAAAA-BBBB-CCCC-DDDD-2EEEEEEEEEEE"));
b.Add(new SqlGuid("2AAAAAAA-BBBB-CCCC-DDDD-1EEEEEEEEEEE"));
b.Add(new SqlGuid("1AAAAAAA-BBBB-CCCC-DDDD-3EEEEEEEEEEE"));
b.Sort();
Console.WriteLine("--Sorted SqlGuids--");
foreach (SqlGuid sg in b)
{
    Console.WriteLine("{0}", sg);
}

这会产生输出：

--Unsorted Guids--
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee
--Sorted Guids--
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
--Sorted SqlGuids--
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee

SqlGuid class 有一个接受 Guid 的构造函数，从一个到另一个的转换也可以，所以它们之间的转换应该很容易。例如在上面的代码中添加以下内容：

List<SqlGuid> c = a.Select(g => new SqlGuid(g)).ToList();
c.Sort();
Console.WriteLine("--Sorted SqlGuids 2--");
foreach (SqlGuid sg2 in c)
{
    Console.WriteLine("{0}", sg2);
}

添加输出：

--Sorted SqlGuids 2--
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee

Answer 2

死灵法术：
答案包括如何，但不包括原因。
因此，仅作记录，SQL-server 按字节顺序对它们进行排序，也就是说自定义字节顺序：

private static readonly int[] x_rgiGuidOrder = new int[16] // 16 Bytes = 128 Bit 
        {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};

换句话说，如果您将 Guid 想象成连续的 UInt128 数字，则需要将其分成 16 个以 256 为基数的块，并将这些块排列在它们的 sort-order 中以产生 SQL-compatible UID。

如果不清楚：

public class SqlGuid
    : System.IComparable
    , System.IComparable<SqlGuid>
    , System.Collections.Generic.IComparer<SqlGuid>
    , System.IEquatable<SqlGuid>
{
    private const int NUM_BYTES_IN_GUID = 16;

    // Comparison orders.
    private static readonly int[] m_byteOrder = new int[16] // 16 Bytes = 128 Bit 
    {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};

    private byte[] m_bytes; // the SqlGuid is null if m_value is null


    public SqlGuid(byte[] guidBytes)
    {
        if (guidBytes == null || guidBytes.Length != NUM_BYTES_IN_GUID)
            throw new System.ArgumentException("Invalid array size");

        m_bytes = new byte[NUM_BYTES_IN_GUID];
        guidBytes.CopyTo(m_bytes, 0);
    }


    public SqlGuid(System.Guid g)
    {
        m_bytes = g.ToByteArray();
    }


    public byte[] ToByteArray()
    {
        byte[] ret = new byte[NUM_BYTES_IN_GUID];
        m_bytes.CopyTo(ret, 0);
        return ret;
    }

    int CompareTo(object obj)
    {
        if (obj == null)
            return 1; // https://msdn.microsoft.com/en-us/library/system.icomparable.compareto(v=vs.110).aspx

        System.Type t = obj.GetType();

        if (object.ReferenceEquals(t, typeof(System.DBNull)))
            return 1;

        if (object.ReferenceEquals(t, typeof(SqlGuid)))
        {
            SqlGuid ui = (SqlGuid)obj;
            return this.Compare(this, ui);
        } // End if (object.ReferenceEquals(t, typeof(UInt128)))

        return 1;
    } // End Function CompareTo(object obj)


    int System.IComparable.CompareTo(object obj)
    {
        return this.CompareTo(obj);
    }


    int CompareTo(SqlGuid other)
    {
        return this.Compare(this, other);
    }


    int System.IComparable<SqlGuid>.CompareTo(SqlGuid other)
    {
        return this.Compare(this, other);
    }


    enum EComparison : int
    {
        LT = -1, // itemA precedes itemB in the sort order.
        EQ = 0, // itemA occurs in the same position as itemB in the sort order.
        GT = 1 // itemA follows itemB in the sort order.
    }


    public int Compare(SqlGuid x, SqlGuid y)
    {
        byte byte1, byte2;

        //Swap to the correct order to be compared
        for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
        {
            byte1 = x.m_bytes[m_byteOrder[i]];
            byte2 = y.m_bytes[m_byteOrder[i]];
            if (byte1 != byte2)
                return (byte1 < byte2) ?  (int) EComparison.LT : (int) EComparison.GT;
        } // Next i 

        return (int) EComparison.EQ;
    }


    int System.Collections.Generic.IComparer<SqlGuid>.Compare(SqlGuid x, SqlGuid y)
    {
        return this.Compare(x, y);
    }


    public bool Equals(SqlGuid other)
    {
        return Compare(this, other) == 0;
    }


    bool System.IEquatable<SqlGuid>.Equals(SqlGuid other)
    {
        return this.Equals(other);
    }


}

这意味着您可以在没有 SqlGuid 的情况下执行此操作，方法是：

public class TestClass 
{
    public static void Test()
    {
        System.Collections.Generic.List<System.Guid> ls = new System.Collections.Generic.List<System.Guid>();
        for(int i = 0; i < 100; ++i)
            ls.Add(System.Guid.NewGuid());

        ls.Sort(Compare);
    }


    public static int Compare(System.Guid x, System.Guid y)
    {
        const int NUM_BYTES_IN_GUID = 16;
        byte byte1, byte2;

        byte[] xBytes = new byte[NUM_BYTES_IN_GUID];
        byte[] yBytes = new byte[NUM_BYTES_IN_GUID];

        x.ToByteArray().CopyTo(xBytes, 0);
        y.ToByteArray().CopyTo(yBytes, 0);

        int[] byteOrder = new int[16] // 16 Bytes = 128 Bit 
            {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};


        //Swap to the correct order to be compared
        for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
        {
            byte1 = xBytes[byteOrder[i]];
            byte2 = yBytes[byteOrder[i]];
            if (byte1 != byte2)
                return (byte1 < byte2) ? -1 : 1;
        } // Next i 

        return 0;
    }

}

尽管使用 SqlGuid 会更有效率，因为 SqlGuid 不需要在每次比较时都re-compute byte-array。

Answer 3

跑题了：看陈峰的How many ways are there to sort GUIDs?

总结为：

Algorithm	Byte array	String
memcmp	00 11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF	{33221100-5544-7766-8899-AABBCCDDEEFF}
System.Guid / string	33 22 11 00 55 44 77 66 88 99 AA BB CC DD EE FF	{00112233-4455-6677-8899-AABBCCDDEEFF}
SqlGuid	CC DD EE FF AA BB 88 99 66 77 00 11 22 33 44 55	{FFEEDDCC-BBAA-9988-6677-001122334455}
Platform::Guid	33 22 11 00 77 66 55 44 BB AA 99 88 FF EE DD CC	{00112233-6677-4455-BBAA-9988FFEEDDCC}

并且 Java 将每个 GUID 视为一对 big-endian 格式的有符号 64 位整数，请参阅 Another way to sort GUIDs: Java。在两列（位 0 和 64）中，排序顺序为 89ABCDEF01234567。在其他列中，排序顺序为 0123456789ABCDEF。

如何在 C# 中对顺序 GUID 进行排序？

How to sort sequential GUIDs in C#?

c#

guid

newsequentialid