在java項目中實現(xiàn)一個樹形選擇排序?相信很多沒有經(jīng)驗的人對此束手無策,為此本文總結了問題出現(xiàn)的原因和解決方法,通過這篇文章希望你能解決這個問題。
樹形選擇排序:又稱錦標賽排序(Tournament Sort),是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關鍵字進行兩兩比較,然后在n/2個較小者之間再進行兩兩比較,如此重復,直至選出最小的記錄為止。
算法實現(xiàn)代碼如下:
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"); } }