归并排序与快速排序

阅前警告

本文内容可能高度抽象，因为这段时间实在太忙，只能大概写个大致想法，想起一个引导的作用，没想过如何组织文章。

归并排序

归并排序的基本思想：要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。其中的“归并”其实也是排序，方法是：通过比较左右两边数组的元素来进行排序。
那么要如何实现这种归并呢？一种简单的办法是使用额外的空间，然后把不同的两个有序数组归并到这一块空间中。但是这样做并不明智，因为每次归并时都需要创建新数组来存储排序结果，所以使用原地归并会更好，即将归并后的结果放回原数组中。（但即便是原地归并，我们仍然需要使用一个和原数组一样大的辅助数组来帮助我们进行归并。）

private static void Merge(T[] a, int lo, int mid, int hi)
{
    int i = lo, j = mid + 1;
	
    for (int k = lo; k <= hi; k++)
    {
        aux[k] = a[k];  // 复制原数组至辅助数组
    }
	
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid)
        {   // 左边处理完毕了
            a[k] = aux[j++];  // 处理右边剩下的元素
        }
        else if (j > hi)
        {   // 右边处理完毕了
            a[k] = aux[i++];  // 处理左边剩下的元素
        }
        else if (Less(aux[i], aux[j]))
        {   // 两边都没处理完毕，且左边元素比右边元素小
            a[k] = aux[i++];  // 把左边元素放回原数组中
        }
        else
        {   // 两边都没处理完毕，且右边元素比左边元素小
            a[k] = aux[j++];  // 把右边元素放回原数组中
        }
    }
}

自顶向下的归并排序

分治思想，递归实现。
Sort方法要做的事情就是将数组尽可能地切分，然后进行归并。

private static void Sort(T[] a, int lo, int hi)
{
    if (hi <= lo)
    {
        return;
    }
    int mid = (lo + hi) / 2;  // or: lo + (hi - lo) / 2
    Sort(a, lo, mid);  // 将左半边排序
    Sort(a, mid + 1, hi);  // 将右半边排序
    Merge(a, lo, mid, hi);  // 归并结果
}

优化方式：

1. 对小规模数组使用插入排序
2. 测试数组是否有序
3. 不将元素复制到辅助数组
   优化后的代码：

   public static new void Sort(T[] a)
   {
       aux = (T[])a.Clone();
       ImprovedSort(aux, a, 0, a.Length - 1);
   }
   
   public static void ImprovedSort(T[] src, T[] dst, int lo, int hi)
   {
       if (hi <= lo + length)
       {   // 对小规模子数组使用插入排序
           for (int i = 1; i <= hi; i++)
           {
               for (int j = i; j > 0 && Less(src[j], src[j - 1]); j--)
               {
                   Exch(src, j, j - 1);
               }
           }
           return;
       }
       int mid = (lo + hi) / 2;  // or: lo + (hi - lo) / 2
       ImprovedSort(dst, src, lo, mid);  // 将左半边排序
       ImprovedSort(dst, src, mid + 1, hi);  // 将右半边排序
       if (!Less(src[mid + 1], src[mid]))  // 如果 a[mid + 1] 大于等于 a[mid]，说明数组是有序的（因为a[mid]为左半部分最大元素，a[mid + 1]为右半部分最小元素）
       {
           Array.Copy(src, lo, dst, lo, hi - lo + 1);
           return;
       }
       ImprovedMerge(src, dst, lo, mid, hi);
   }
   
   private static void ImprovedMerge(T[] src, T[] dst, int lo, int mid, int hi)
   {
       int i = lo, j = mid + 1;
   
       for (int k = lo; k <= hi; k++)
       {
           if (i > mid)
           {   // 左边处理完毕了
               dst[k] = src[j++];  // 处理右边剩下的元素
           }
           else if (j > hi)
           {   // 右边处理完毕了
               dst[k] = src[i++];  // 处理左边剩下的元素
           }
           else if (Less(src[i], src[j]))
           {   // 两边都没处理完毕，且左边元素比右边元素小
               dst[k] = src[i++];  // 把左边元素放回原数组中
           }
           else
           {   // 两边都没处理完毕，且右边元素比左边元素小
               dst[k] = src[j++];  // 把右边元素放回原数组中
           }
       }
   }

   这里最需要注意的点就是弄清楚两个数组的交换。src是 source 的缩写，也就是源；dst是 destination 的缩写，也就是目标。最后排好序的是目标，不是源，别搞错了。

自底向上的归并排序

同样的，也是分治思想，但是迭代实现。先归并好所有的小数组，然后增大数组，再归并增大后的所有数组，继续增大，继续归并…如此继续下去直至归并完成。
但是需要注意的是最后一个数组的长度可能会小于我们设定的要进行归并的子数组的长度，所以写代码的时候不要忘记这点。

public static new void Sort(T[] a)
{
    int length = a.Length;
    aux = new T[length];
    for (int sz = 1; sz < length; sz += sz)  // sz为需要归并的子数组的大小
    {
        for (int lo = 0; lo < length - sz; lo += sz + sz)  // lo为子数组的索引
        {
            Merge(a, lo, lo + sz - 1, Math.Min((lo + sz + sz - 1), length - sz - 1));
        }
    }
}

快速排序

分治思想，递归实现。
基本思路：选择一个“锚点”（pivot），一般选择打乱后（打乱是为了避免最差情况）的数组中的第一个元素；基于这个锚点，用双指针分别从左右边界开始，扫描元素，左边直到找到一个比pivot大的元素或是越界后停下，右边直到找到一个比pivot小的元素或是越界后停下，检查左指针是否小于右指针，若是，交换两个元素，重复此行为至扫描结束；
扫描结束后，需要把基准元素放在正确的位置上，也就是数组开头元素跟右指针上的元素进行交换，因为扫描结束后右指针指向的元素是小于pivot的；现在，在pivot左边的元素都小于pivot，在pivot右边的元素都大于pivot了，之后，再根据这个右指针的值（也就是pivot的位置），将数组切分成左右两个子数组，再对左右子数组进行找pivot排序的操作，如此递归下去，最后就能得到排好序的原数组了。

public class Quick<T> : Sorts<T> where T : IComparable<T>
{
    public static new void Sort(T[] a)
    {
        Sort(a, 0, a.Length - 1);
    }

    public static void Sort(T[] a, int lo, int hi)
    {
        if (lo >= hi)
        {
            return;  // 单个元素不需要排序
        }
        int j = Partition(a, lo, hi);  // 切分，这一步之后，j 左边的元素都小于 j，j 右边的元素都大于 j
        Sort(a, lo, j - 1);  // 递归调用，将左半部分排序
        Sort(a, j + 1, hi);  // 递归调用，将右半部分排序
    }

    public static int Partition(T[] a, int lo, int hi)
    {   // 将数组切分为 a[lo, i - 1], a[i], a[i + 1, hi]
        int i = lo, j = hi + 1;  // 左右扫描指针
        T pivot = a[lo];  // 基准，即切分元素
        while (true)
        {   // 扫描左右，检查扫描是否结束并交换元素
            while (Less(a[++i], pivot))
            {
                if (i == hi)
                {
                    break;
                }
            }
            while (Less(pivot, a[--j]))
            {
                if (j == lo)
                {
                    break;
                }
            }
            if (i >= j)
            {
                break;
            }
            Exch(a, i, j);
        }
        Exch(a, lo, j);  // 将基准元素放到正确的位置上
        return j;  // a[lo, j - 1] <= a[j] <= a[j + 1, hi]达成
    }
}

如何优化：

• 切换到插入排序：跟归并排序一样，对小数组使用插入排序。
• 三切分取样：使用子数组的一小部分元素的中位数来切分数组。
• 熵最优的排序：改进算法在一个元素全部重复的子数组下继续切分为更小数组的情况。

这里先讨论最后一个优化的实现方法。一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素，然后要排序的就是两边的元素，这样就能避免重复元素排序了。
这里介绍 Dijkstra 的解法：维护三个指针lf、i和gt，其中，lt使得a[lo...lt - 1]中的元素都小于pivot，gt使得a[gt + 1...hi]中的元素都大于pivot，i使得a[lt...i - 1]中的元素等于pivot，a[i...gt]中的元素还未确定。代码如下：

public class Quick3way<T> : Sorts<T> where T : IComparable<T>
{
    public static new void Sort(T[] a)
    {
        Sort(a, 0, a.Length - 1);
    }

    public static void Sort(T[] a, int lo, int hi)
    {
        if (lo >= hi)
        {
            return;
        }
        int lt = lo, i = lo + 1, gt = hi;  // 维护三个指针
        T pivot = a[lo];
        while (i <= gt)
        {
            int tmp = a[i].CompareTo(pivot);  // 用一个临时变量保存比较结果
            if (tmp < 0)
            {   // 如果 a[i] 小于 pivot，那就换去左边
                Exch(a, i++, lt++);
            }
            if (tmp > 0)
            {   // 如果 a[i] 大于 pivot，那就换去右边
                Exch(a, i, gt--);
            }
            else
            {   // 如果 a[i] 等于 pivot，不需交换，直接 i++ 即可
                i++;
            }
        }
        // 至此，a[lo...lt - 1] < pivot = a[lt...gt] < a[gt + 1...hi] 成立
        Sort(a, lo, lt - 1);
        Sort(a, gt + 1, hi);
    }
}

然后是根据第一点和第二点改进的二路快速排序算法：

public class OptimizedQuick<T> : Sorts<T> where T : IComparable<T>
{
    private const int LENGTH = 9;

    public static new void Sort(T[] a)
    {
        Sort(a, 0, a.Length - 1);
    }

    private static void Sort(T[] a, int lo, int hi)
    {
        if (lo >= hi)
        {
            return;
        }
        int n = hi - lo + 1;
        if (n <= LENGTH)
        {   // 对小规模数组使用插入排序
            Insertion<T>.Sort(a, lo, hi + 1);
            return;
        }
        int j = Partion(a, lo, hi);
        Sort(a, lo, j - 1);
        Sort(a, j + 1, hi);
    }

    private static int Partion(T[] a, int lo, int hi)
    {
        // 三切分取样
        int n = Median3(a, lo, (hi + lo + 1) / 2, hi);
        Exch(a, lo, n);

        int i = lo, j = hi + 1;
        T pivot = a[lo];

        while (Less(a[++i], pivot))
        {   // pivot 是其中最大的元素
            if (i == hi)
            {
                Exch(a, lo, hi);
                return hi;
            }
        }

        while (Less(pivot, a[--j]))
        {   // pivot 是其中最小的元素
            if (j == lo + 1)
            {
                return lo;
            }
        }

        while (i < j)
        {
            Exch(a, i, j);
            while (Less(a[++i], pivot)) ;
            while (Less(pivot, a[--j])) ;
        }

        Exch(a, lo, j);
        return j;
    }

    private static int Median3(T[] a, int i, int j, int k)
    {   // 返回三个元素中的中位数
        return (Less(a[i], a[j]) ?
               (Less(a[j], a[k]) ? j : Less(a[i], a[k]) ? k : i) :
               (Less(a[k], a[j]) ? j : Less(a[k], a[i]) ? k : i));
    }
}

最后是三点结合起来，也就是改进的三路快速排序算法：

测试方法

尝试写一个从文本中读取待排序的内容的方法。本来想写好一点不过还是偷懒了，将就测试一下吧。

/// <summary>
/// 向文件 TestData.txt 中随机写入 N 个数，每写入十个数便换一次行
/// </summary>
static void WriteRandomNumber()
{
    // 设定生成测试数据的大小
    const long N = 100000;
    const int left = -10000;
    const int right = 10000;

    // 重置测试数据文件
    if (File.Exists("TestData.txt"))
    {
        File.Delete("TestData.txt");
    }

    // 生成测试用数据
    using FileStream sw = new FileStream("TestData.txt", FileMode.Append);  // 其实用 StreamWriter 会更好
    Random random = new Random();
    try
    {
        for (int i = 1; i <= N; i++)
        {
            if (i % 20 == 0)
            {
                sw.Write(Encoding.UTF8.GetBytes($"{random.Next(left, right)}\r\n"));
            }
            else
            {
                sw.Write(Encoding.UTF8.GetBytes($"{random.Next(left, right)} "));
            }
        }
    }
    catch (Exception e)
    {
        Console.WriteLine($"{e.Message}");
    }
}

/// <summary>
/// 从文件中读取数字转为 int 数组并排序
/// </summary>
static void ReadFromFileAndSort()
{
    string? tmp;
    ArrayList numsList = new();
    const string fileName = "TestData.txt";
    Stopwatch sw = new Stopwatch();

    try
    {
        // 读取数字至数组
        using StreamReader sr = new StreamReader(fileName);
        while (!string.IsNullOrEmpty(tmp = sr.ReadLine()))
        {
            numsList.AddRange(Array.ConvertAll(tmp.Split(" "), int.Parse));
        }

        // 转换数组类型
        int[] numsArray = (int[])numsList.ToArray(typeof(int));

        // 对数组进行排序
        Console.WriteLine(Sorts<int>.IsSoreted(numsArray));
        sw.Start();
        Quick<int>.Sort(numsArray);
        Console.WriteLine(sw.ElapsedMilliseconds);
        Console.WriteLine(Sorts<int>.IsSoreted(numsArray));
    }
    catch (FileNotFoundException e)
    {
        Console.WriteLine($"Cannot find the file named \"{fileName}\"");
    }
    catch (FormatException e)
    {
        Console.WriteLine($"Cannot convert to a num : {e.Message}");
    }

}

---

希望本文章能够帮到您~