C# List.Sort 探究

C#中Sort的排序实现

MSDN.aspx)

此方法使用 Array.Sort 方法,后者适用反省排序,如下所示︰

  • 如果分区大小少于 16 个元素,它使用插入排序算法。
  • 如果分区数超过 2 * LogN,其中 N 是范围的输入数组,它使用 Heapsort 算法。
    否则,它使用快速排序算法。

此实现将执行不稳定排序 也就是说,如果两个元素相等,可能不会保留它们的顺序.
与此相反,稳定排序保留相等的元素的顺序。

  • 一般情况下,此方法为 O (n log n) 操作,其中 n 是 Count; 最坏的情况是 O (n ^2) 操作。

插入排序 (Insertion Sort)

原文连接

00c37c01-098a-43c4-bd6c-660a00e35404

快速排序 (Quick Sort)

原文连接

45cf8e7b-6be1-4eb6-9be3-500494650

堆排序 (Heap Sort)

原文连接

d99c5742-7e13-426b-a1cf-0be34c0228b9

33085f44-157c-4b99-b50b-cc4874278e38

总结

个人理解

插入排序 (Insertion Sort)

最简单,适合小数量元素排序
快速排序 (Quick Sort)

快速排序 (Quick Sort)

主旨就是将所有元素切块分成 [小于A],[A],[大于A] 然后再递归小于A和大于A的两部分 直到最终排序完成
堆排序 (Heap Sort)

堆排序 (Heap Sort)

从树的最后一个节点(数组的最后一位)开始,进行Build-Max-Heap然后递归的index-1,再继续次操作.

疑惑

如果按CSDN中所说,内部排序是根据待排序元素的多少进行选择最终排序算法.
按上面三种排序的话,在list.Sort((x,y)=>{...})函数中,理论不应该存在x,y是同一个元素的情况.
所以之前代码中比较函数写的都是x>y?1:-1这样排序会不准.

应该改为

1
2
if(x==y)return 0;
return x>y?1:-1

Unity中测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class TSortData
{
public int UID;
public int sortIndex;
}

var list = new List<TSortData>();
for (var i = 0; i < 30; i++)
{
var data = new TSortData
{
UID = i,
sortIndex = Random.Range(10, 99)
};
list.Add(data);
}

list.Sort((x, y) =>
{
if (x.UID == y.UID)
{
Debug.LogFormat("Sort x,y is the same element <color=red>UID = {0}</color>, sortIndex = {1}", x.UID, x.sortIndex);
}
return x.sortIndex > y.sortIndex ? 1 : -1;
});

结果

61268421

坚持原创技术分享,您的支持将鼓励我继续创作!