2.5.27

2.5.27 #

解答 #

类似于索引排序的做法,访问数组都通过一层索引来间接实现。

首先创建一个数组 index,令 index[i] = i

排序时的交换变成 index 数组中元素的交换,

读取元素时使用 a[index[i]] 而非 a[i]

代码 #

// 间接排序。
static int[] IndirectSort<T>(T[] keys) where T : IComparable<T>
{
    var n = keys.Length;
    var index = new int[n];
    for (var i = 0; i < n; i++)
        index[i] = i;

    for (var i = 0; i < n; i++)
    for (var j = i; j > 0 && keys[index[j]].CompareTo(keys[index[j - 1]]) < 0; j--)
    {
        var temp = index[j];
        index[j] = index[j - 1];
        index[j - 1] = temp;
    }

    return index;
}