2.2.9 #
解答 #
官方给出的归并排序实现中在 Sort 方法里初始化了 aux 数组。
源码见：https://algs4.cs.princeton.edu/22mergesort/Merge.java.html
C#实现和官方的实现非常类似，
首先定义只接受一个参数的公开 Sort 方法，在这个方法里面初始化 aux 数组。
/// <summary>
/// 利用归并排序将数组按升序排序。
/// </summary>
/// <typeparam name="T">数组元素类型。</typeparam>
/// <param name="a">待排序的数组。</param>
public override void Sort<T>(T[] a)
{
T[] aux = new T[a.Length];
Sort(a, aux, 0, a.Length - 1);
}
然后建立一个私有的递归 Sort 方法做实际的排序操作。
/// <summary>
/// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。
/// </summary>
/// <typeparam name="T">需要排序的元素类型。</typeparam>
/// <param name="a">原数组。</param>
/// <param name="aux">辅助数组。</param>
/// <param name="lo">排序范围起点。</param>
/// <param name="hi">排序范围终点。</param>
private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
{
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
Sort(a, aux, lo, mid);
Sort(a, aux, mid + 1, hi);
Merge(a, aux, lo, mid, hi);
}
代码 #
public class MergeSort : BaseSort
{
/// <summary>
/// 利用归并排序将数组按升序排序。
/// </summary>
/// <typeparam name="T">数组元素类型。</typeparam>
/// <param name="a">待排序的数组。</param>
public override void Sort<T>(T[] a)
{
var aux = new T[a.Length];
Sort(a, aux, 0, a.Length - 1);
}
/// <summary>
/// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。
/// </summary>
/// <typeparam name="T">需要排序的元素类型。</typeparam>
/// <param name="a">原数组。</param>
/// <param name="aux">辅助数组。</param>
/// <param name="lo">排序范围起点。</param>
/// <param name="hi">排序范围终点。</param>
private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T>
{
if (hi <= lo)
return;
var mid = lo + (hi - lo) / 2;
Sort(a, aux, lo, mid);
Sort(a, aux, mid + 1, hi);
Merge(a, aux, lo, mid, hi);
}
/// <summary>
/// 将指定范围内的元素归并。
/// </summary>
/// <typeparam name="T">数组元素类型。</typeparam>
/// <param name="a">原数组。</param>
/// <param name="aux">辅助数组。</param>
/// <param name="lo">范围起点。</param>
/// <param name="mid">范围中点。</param>
/// <param name="hi">范围终点。</param>
private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T>
{
for (var k = lo; k <= hi; k++)
{
aux[k] = a[k];
}
int i = lo, j = mid + 1;
for (var k = lo; k <= hi; k++)
{
if (i > mid)
{
a[k] = aux[j];
j++;
}
else if (j > hi)
{
a[k] = aux[i];
i++;
}
else if (Less(aux[j], aux[i]))
{
a[k] = aux[j];
j++;
}
else
{
a[k] = aux[i];
i++;
}
}
}
}