溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
在java項目中實現一個樹形選擇排序？相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
樹形選擇排序：又稱錦標賽排序（Tournament Sort），是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關鍵字進行兩兩比較，然后在n/2個較小者之間再進行兩兩比較，如此重復，直至選出最小的記錄為止。
算法實現代碼如下：
package exp_sort;
public class TreeSelectSort {
public static 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;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
TreeSelectionSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
}算法分析：
在樹形選擇排序中，除了最小的關鍵字，被選出的最小關鍵字都是走了一條由葉子結點到跟節點的比較過程，由于含有n個葉子結點的完全二叉樹的深度log2n+1,因此在樹形選擇排序中，每選出一個較小關鍵字需要進行log2n次比較，所以其時間復雜度是O(nlog2n)，移動記錄次數不超過比較次數，故總的算法時間復雜度為O(nlog2n)，與簡單選擇排序算法相比，降低了比較次數的數量級，增加了n-1個額外的存儲空間存放中間比較結果。
補充：
這里再來介紹對樹形選擇排序的改進算法，即堆排序算法。
堆排序彌補了樹形選擇排序算法占用空間多的缺憾。采用堆排序時，只需要一個記錄大小的輔助空間。
算法思想是：
把待排序記錄的關鍵字存放在數組r[1...n]中，將r看成是一棵完全二叉樹的順序表示，每個結點表示一個記錄，第一個記錄r[1]作為二叉樹的根，以下每個記錄r[2...n]依次逐層從左到右順序排列，任意結點r[i]的左孩子是r[2*i]，右孩子是r[2*i+1]；雙親是r[[i/2]]。
堆定義：各結點的關鍵字值滿足下列條件：
r[i].key >= r[2i].key 且 r[i].key >= r[2i+1].key (i=1,2,……[i/2])
滿足上面條件的完全二叉樹稱為大根堆；相反，如果這顆完全二叉樹中任意結點的關鍵字小于或者等于其左孩子和右孩子的關鍵字，對應的堆叫做小根堆。
堆排序的過程主要需要解決兩個問題：第一個是，按照堆定義建初堆；第二個是，去掉最大元后重建堆，得到次大元。
堆排序即是利用堆的特性對記錄序列進行排序,過程如下：
1、對給定序列建堆；
2、輸出堆頂；(首元素與尾元素交換)
3、對剩余元素重建堆；(篩選首元素)
4、重復2，3，直至所有元素輸出。
注意：“篩選”須從第[n/2]個結點開始，逐層向上倒退，直到根結點。
算法分析：
1. 對深度為 k 的堆，“篩選”所需進行的關鍵字比較的次數至多為2(k-1)；
2. n 個關鍵字的堆深度為 [log2n]+1, 初建堆所需進行的關鍵字比較的次數至多為：n* [log2n];
3. 重建堆 n-1 次，所需進行的關鍵字比較的次數不超過：(n-1)*2 [log2n ];
因此，堆排序在最壞情況下，其時間復雜度為O(nlog2n)，這是堆排序的最大優點。
看完上述內容，你們掌握在java項目中實現一個樹形選擇排序的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
