樹形選擇排序

Selection #region >return

樹形選擇排序（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&#91;&#93; TreeSelectionSort(int&#91;&#93; mData)
{
int TreeLong = mData.Length * 4;
int MinValue = -10000;
int&#91;&#93; tree = new int&#91;TreeLong&#93;; // 樹的大小
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&#91;treeSize - i&#93; = mData&#91;i&#93;;
}
for (; i < baseSize; i++)
{
tree&#91;treeSize - i&#93; = MinValue;
}
// 構造一棵樹
for (i = treeSize; i > 1; i -= 2)
{
tree&#91;i / 2&#93; = (tree&#91;i&#93; > tree&#91;i - 1&#93; ? tree&#91;i&#93; : tree&#91;i - 1&#93;);
}
n -= 1;
while (n != -1)
{
max = tree&#91;1&#93;;
mData&#91;n--&#93; = max;
maxIndex = treeSize;
while (tree&#91;maxIndex&#93; != max)
{
maxIndex--;
}
tree&#91;maxIndex&#93; = MinValue;
while (maxIndex > 1)
{
if (maxIndex % 2 == 0)
{
tree&#91;maxIndex / 2&#93; = (tree&#91;maxIndex&#93; > tree&#91;maxIndex + 1&#93; ? tree&#91;maxIndex&#93; : tree&#91;maxIndex + 1&#93;);
}
else
{
tree&#91;maxIndex / 2&#93; = (tree&#91;maxIndex&#93; > tree&#91;maxIndex - 1&#93; ? &#8205;tree&#91;maxIndex&#93; : tree&#91;maxIndex - 1&#93;);
}
maxIndex /= 2;
}
}
return mData;
}
#endregion