Array.Sort()是在我们日常工作中非常常用的函数，不需要自己编写排序算法就可以方便的对数组进行排序。
利用Array.Sort()排序具有以下特点：
- 排序是不稳定的
- 采用内省排序（introspective sort）
这里简单解释一下内省排序。内省排序会先以快速排序开始。在之前的文章分割链表中，我们接触过快速排序。快速排序采用分治的思想，通过某一分界值将数组分成左右两部分，将大于等于分界值的数据集中到右侧，将小于分界值的数据集中到左侧。然后分别对左侧右侧进行上述处理，直到每一侧都排好序，那么整体也就排好序了。这一过程是一个递归的过程，如果数组很大，那么有可能该递归的深度会很深。最差情况，快排的时间复杂度会达到。而在内省排序中，当递归超过某一个深度d时，则会针对该深度d上的每一个划分利用不同方法进行排序。
- 如果划分的大小小于16个元素，对该划分使用插入排序
- 如果划分的大小超过2LogN， N是数组长度，那么就使用堆排序
-
如果划分的大小介于两者之间，则在该划分上继续使用快速排序
如下图所示，在对原数组快速排序递归到某一深度时，对于小于16个元素的数组使用插入排序，对数组长度大于2LogN的数组采用堆排序，对介于两者之间的数组仍然使用快速排序。我们可以看到，通过这种方式，我们避免了在更大数组上继续使用快速排序，从而避免了快速排序最坏情况的出现。
我们可以认为在内省排序中时间复杂度依然是。
关于Array.Sort()的更详细介绍可以参考 https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?view=netframework-4.8
直接使用Array.Sort()会得到一个从小到大的排序好的结果。如果我们想得到一个从大到小排序好的结果我们要怎么办呢？这里主要介绍三种方法。
using System;
using System.Collections;
using System.Linq;
namespace SortPractice
{
public class IntReverseComparer : IComparer
{
public int Compare(object x, object y)
{
return (new CaseInsensitiveComparer()).Compare(y, x);
}
}
class Program
{
static void Main(string[] args)
{
int[] arr1 = new int[] { 1, 9, 6, 7, 5, 9 };
// 方法1：利用Comparison委托函数
Array.Sort(arr1, new Comparison<int>((i1, i2) => i2.CompareTo(i1)));
foreach(var a in arr1)
{
Console.Write(a + " ");
}
Console.WriteLine();
// 方法2：利用ICompare接口
int[] arr2 = new int[] { 1, 9, 6, 7, 5, 9 };
Array.Sort(arr2, new IntReverseComparer());
foreach(var a in arr2)
{
Console.Write(a + " ");
}
Console.WriteLine();
// 方法3：直接利用LINQ的OrderByDescending方法
int[] arr3 = new int[] { 1, 9, 6, 7, 5, 9 };
arr3 = arr3.OrderByDescending(c => c).ToArray();
foreach (var a in arr2)
{
Console.Write(a + " ");
}
Console.WriteLine();
}
}
}
在上面的代码中，第一种方法是利用Comparison委托函数。我们利用lamba expression来构建这个委托函数。如果我们用i1.CompareTo(i2)表示，则仍然是从小到大排序，将i1，i2互换后则变为从大到小排序。
第二种方法则是自己实现一个Comparer类，该类需要实现IComparer接口，并实现其中的Compare方法。
第三种方法则是直接利用LINQ中的OrderByDescending方法。
总结
Array.Sort()作为C#中常用的排序算法，还是需要进行重点掌握的，这样我们就可以根据自己的具体需要编写自定义比较函数，从而方便快捷高效的解决日常开发中的各种排序问题了。
网友评论