CS4L16——List排序

本章代码关键字

1
2
3
4
list<>.Sort()    // List的排序方法
IComparable<>    // 自定义类继承此接口并实现方法后，其List<>即可直接Sort()
CompareTo()        // IComparable<>需要实现的方法
Comparison<>    // 参数为两个待比较的同类型对象，返回值为int类型排序结果的委托，可以传入到Sort()内，即可直接使用排序方法

List 自带排序方法

​List<>​ 自带了 Sort()​ 方法，排序结果默认是升序的，ArrayList​ 中也有 Sort​ 排序方法

系统自带的变量（int​，float​，double​…）一般都可以直接 Sort​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
List<int> list = new List<int>() { 3, 2, 6, 1, 4, 5 };
string info = "排序前：";
for (int i = 0; i < list.Count; i++)
{
    info += list[i];
    info += ",";
}
Console.WriteLine(info);

//list提供的排序方法(默认升序)
list.Sort();
info = "排序后：";
for (int i = 0; i < list.Count; i++)
{
    info += list[i];
    info += ",";
}
Console.WriteLine(info);

输出：

1
2
排序前：3,2,6,1,4,5,
排序后：1,2,3,4,5,6,

自定义类的排序

对于下面这种自定义类，List<>​ 自带的 Sort()​ 方法是不能直接排序的，会报错

1
2
3
4
5
6
7
8
class Item
{
    public int money;
    public Item(int money)
    {
        this.money = money;
    }
}
1
2
3
4
5
6
7
8
List<Item> itemList = new List<Item>();
itemList.Add(new Item(45));
itemList.Add(new Item(10));
itemList.Add(new Item(99));
itemList.Add(new Item(24));
itemList.Add(new Item(100));
itemList.Add(new Item(12));
itemList.Sort();

输出（报错信息）：

1
2
3
4
5
6
7
8
9
10
11
12
Unhandled exception. System.InvalidOperationException: Failed to compare two elements in the array.
 ---> System.ArgumentException: At least one object must implement IComparable.
   at System.Collections.Comparer.Compare(Object a, Object b)
   at System.Collections.Generic.ArraySortHelper`1.InsertionSort(Span`1 keys, Comparison`1 comparer)
   at System.Collections.Generic.ArraySortHelper`1.IntroSort(Span`1 keys, Int32 depthLimit, Comparison`1 comparer)
   at System.Collections.Generic.ArraySortHelper`1.IntrospectiveSort(Span`1 keys, Comparison`1 comparer)
   at System.Collections.Generic.ArraySortHelper`1.Sort(Span`1 keys, IComparer`1 comparer)
   --- End of inner exception stack trace ---
   at System.Collections.Generic.ArraySortHelper`1.Sort(Span`1 keys, IComparer`1 comparer)
   at System.Array.Sort[T](T[] array, Int32 index, Int32 length, IComparer`1 comparer)
   at System.Collections.Generic.List`1.Sort(Int32 index, Int32 count, IComparer`1 comparer)
   at Program.<Main>$(String[] args) in e:\CodeField\CSharpProjects\CSharpTest\Program.cs:line 8

如果要让自定义类的 List​ 可以被排序，则该类必须要继承 IComparable<>​接口！
（也可以使用 IComparable​ 接口，但是这个接口没有泛型，用的是 object​）

接口定义如下（这里的 T?​ 是可空的意思，代表传入的 other​ 可能是 null​，需要判断（#TODO#​），in​ 是协变逆变的内容（#TODO#​））：

1
2
3
4
public interface IComparable<in T>
{
    int CompareTo(T? other);
}

因此，我们需要在自定义类实现 CompareTo​ 方法，并按照接口要求返回规定的 int​ 返回值，其中返回值的含义为：

  • 小于 0：放在传入对象的前面
  • 等于 0：保持当前位置不变
  • 大于 0：放在传入对象的后面

可以简单理解为传入对象的位置，就是0

  • 如果返回值为负，就放在传入对象的左边，也就是前面
  • 如果返回值为正，就放在传入对象的右边，也就是后面
  • 如果返回值为 0，位置就不变

可以用坐标轴去记忆，负数在左，正数在右

假设自定义的 Item​ 类以 money​ 的大小来排列，那么 Item​ 的 CompareTo​ 实现为：

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
class Item : IComparable<Item>
{
    public int money;
  
    public Item(int money)
    {
        this.money = money;
    }

    public int CompareTo(Item? other)
    {
        if (other == null)
        {
            return 0;
        }
        else if (this.money > other.money)
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }
}

此时再进行排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<Item> itemList = new List<Item>();
itemList.Add(new Item(45));
itemList.Add(new Item(10));
itemList.Add(new Item(99));
itemList.Add(new Item(24));
itemList.Add(new Item(100));
itemList.Add(new Item(12));
string info = "排序前：";
for (int i = 0; i < itemList.Count; i++)
{
    info += itemList[i].money;
    info += ",";
}
Console.WriteLine(info);

//list提供的排序方法(默认升序)
itemList.Sort();
info = "排序后：";
for (int i = 0; i < itemList.Count; i++)
{
    info += itemList[i].money;
    info += ",";
}
Console.WriteLine(info);

输出：

1
2
排序前：45,10,99,24,100,12,
排序后：10,12,24,45,99,100,

通过委托函数进行排序

如果要在不修改类定义的情况下让自定义类可以使用 List<>​ 排序，除去继承 IComparable​ 接口，还有一种更简单的方法，
即使用 List<T>.Sort()​ 的重载方法： void Sort(Comparison<T> comparison)​ 去排序，其中 Comparison<>​ 是一个委托，定义如下：

1
public delegate int Comparison<in T>(T x, T y);

使用委托来让 List<>.Sort()​ 排序是一种更灵活的做法，相比 IComparable​ 接口，它可以同时利用自定义类的不同属性去做排序

以下方的自定义类为例

1
2
3
4
5
6
7
8
class ShopItem
{
    public int id;
    public ShopItem(int id)
    {
        this.id = id;
    }
}

假设要在不修改上述代码的情况下，使用委托让 List<ShopItem>​ 可以使用 Sort​，需要定义如下方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int SortShopItem(ShopItem a, ShopItem b)
{
    if (a.id > b.id)
    {
        return 1;
    }
    else if (a.id < b.id)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

将这个方法传入到 Sort​ 方法内，就可以直接使用排序了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<ShopItem> shopItems = new List<ShopItem>();
shopItems.Add(new ShopItem(2));
shopItems.Add(new ShopItem(1));
shopItems.Add(new ShopItem(4));
shopItems.Add(new ShopItem(3));
shopItems.Add(new ShopItem(6));
shopItems.Add(new ShopItem(5));
string info = "排序前：";
for (int i = 0; i < shopItems.Count; i++)
{
    info += shopItems[i].id;
    info += ",";
}
Console.WriteLine(info);

//list提供的排序方法(默认升序)
shopItems.Sort(SortShopItem);
info = "排序后：";
for (int i = 0; i < shopItems.Count; i++)
{
    info += shopItems[i].id;
    info += ",";
}
Console.WriteLine(info);

输出：

1
2
排序前：2,1,4,3,6,5,
排序后：1,2,3,4,5,6,

如果要不额外定义函数，还可以使用 lambda 表达式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<ShopItem> shopItems = new List<ShopItem>();
shopItems.Add(new ShopItem(2));
shopItems.Add(new ShopItem(1));
shopItems.Add(new ShopItem(4));
shopItems.Add(new ShopItem(3));
shopItems.Add(new ShopItem(6));
shopItems.Add(new ShopItem(5));
string info = "排序前：";
for (int i = 0; i < shopItems.Count; i++)
{
    info += shopItems[i].id;
    info += ",";
}
Console.WriteLine(info);

//list提供的排序方法(默认升序)
shopItems.Sort((a, b) => { return a.id > b.id ? 1 : -1; });
info = "排序后：";
for (int i = 0; i < shopItems.Count; i++)
{
    info += shopItems[i].id;
    info += ",";
}
Console.WriteLine(info);

因为 lambda 表达式只有一行，因此可以进一步简写为：

1
shopItems.Sort((a, b) => a.id > b.id ? 1 : -1);