樹形選擇排序

樹形選擇排序又稱錦標賽排序（Tournament Sort），是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關鍵字進行兩兩比較，然後在n/2個較小者之間再進行兩兩比較，如此重複，直至選出最小的記錄為止。

基本介紹

• 中文名：樹形選擇排序
• 外文名：Tree Selection Sort
• 別名：錦標賽排序
• 性質：選擇排序的方法

基本概念

樹形選擇排序（Tree Selection Sort），是一種按照錦標賽的思想進行選擇排序的方法。此方法在計算機運算中，是以程式命令體現完成，最後來達到理想的排序目的。

方法說明

樹形選擇排序（Tree Selection Sort），這個過程可用一棵有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