树形选择排序（Tree Selection Sort）

树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

这个过程可用一棵有n个叶子结点的完全二叉树表示。例如，图表2中的二叉树表示从8个数中选出最小数的过程。8个叶子结点到根接点中的关键字，每个非终端结点中的数均等于其左右孩子结点中较小的数值，则根结点中的数即为叶子结点的最小数。在输出最小数之后，割据关系的可传递性，欲选出次小数，仅需将叶子结点中的最小数（13）改为“最大值”，然后从该叶子接点开始，和其左（或右）兄弟的数值进行比较，修改从叶子结点到根的路径上各结点的数，则根结点的数值即为最小值。同理，可依次选出从小到大的所有数。由于含有n个子结点的完全二叉树的深度为log2n+1，则在树形选择排序中，除了最小数值之外，每选择一个次小数仅需要进行log2n次比较，因此，它的时间复杂度为O(nlogn)。但是，这种排序方法尚有辅助存储空间较多、和“最大值”进行多余比较等缺点。为了弥补，威洛姆斯（J. willioms）在1964年提出了另一种形式的选择排序——堆排序。

#region "树形选择排序"

/// <summary>

/// 树形选择排序，Powered By 思念天灵

/// </summary>

/// <param name="mData">待排序的数组</param>

/// <returns>已排好序的数组</returns>

public int[] TreeSelectionSort(int[] mData)

{

int TreeLong = mData.Length * 4;

int MinValue = -10000;

int[] tree = new int[TreeLong]; // 树的大小

int baseSize;

int i;

int n = mData.Length;

int max;

int maxIndex;

int treeSize;

baseSize = 1;

while (baseSize < n)

{

baseSize *= 2;

}

treeSize = baseSize * 2 - 1;

for (i = 0; i < n; i++)

{

tree[treeSize - i] = mData[i];

}

for (; i < baseSize; i++)

{

tree[treeSize - i] = MinValue;

}

// 构造一棵树

for (i = treeSize; i > 1; i -= 2)

{

tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);

}

n -= 1;

while (n != -1)

{

max = tree[1];

mData[n--] = max;

maxIndex = treeSize;

while (tree[maxIndex] != max)

{

maxIndex--;

}

tree[maxIndex] = MinValue;

while (maxIndex > 1)

{

if (maxIndex % 2 == 0)

{

tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex] : tree[maxIndex + 1]);

}

else

{

tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex] : tree[maxIndex - 1]);

}

maxIndex /= 2;

}

}

return mData;

}

#endregion