在java項(xiàng)目中實(shí)現(xiàn)一個(gè)樹形選擇排序

在java項(xiàng)目中實(shí)現(xiàn)一個(gè)樹形選擇排序？相信很多沒有經(jīng)驗(yàn)的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

樹形選擇排序：又稱錦標(biāo)賽排序（Tournament Sort），是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。首先對n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在n/2個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小的記錄為止。

算法實(shí)現(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;
  }
  // 構(gòu)造一棵樹
  for (i = treeSize; i > 1; i -= 2) {
   tree[i / 2] = (tree[i] > tree[i - 1] &#63; 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] &#63; tree[maxIndex]
       : tree[maxIndex + 1]);
    } else {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] &#63; 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");
 }
}

算法分析：

在樹形選擇排序中，除了最小的關(guān)鍵字，被選出的最小關(guān)鍵字都是走了一條由葉子結(jié)點(diǎn)到跟節(jié)點(diǎn)的比較過程，由于含有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹的深度log2n+1,因此在樹形選擇排序中，每選出一個(gè)較小關(guān)鍵字需要進(jìn)行l(wèi)og2n次比較，所以其時(shí)間復(fù)雜度是O(nlog2n)，移動記錄次數(shù)不超過比較次數(shù)，故總的算法時(shí)間復(fù)雜度為O(nlog2n)，與簡單選擇排序算法相比，降低了比較次數(shù)的數(shù)量級，增加了n-1個(gè)額外的存儲空間存放中間比較結(jié)果。

補(bǔ)充：

這里再來介紹對樹形選擇排序的改進(jìn)算法，即堆排序算法。

堆排序彌補(bǔ)了樹形選擇排序算法占用空間多的缺憾。采用堆排序時(shí)，只需要一個(gè)記錄大小的輔助空間。

算法思想是：

把待排序記錄的關(guān)鍵字存放在數(shù)組r[1...n]中，將r看成是一棵完全二叉樹的順序表示，每個(gè)結(jié)點(diǎn)表示一個(gè)記錄，第一個(gè)記錄r[1]作為二叉樹的根，以下每個(gè)記錄r[2...n]依次逐層從左到右順序排列，任意結(jié)點(diǎn)r[i]的左孩子是r[2*i]，右孩子是r[2*i+1]；雙親是r[[i/2]]。

堆定義：各結(jié)點(diǎn)的關(guān)鍵字值滿足下列條件：

r[i].key >= r[2i].key 且 r[i].key >= r[2i+1].key   (i=1,2,……[i/2])

滿足上面條件的完全二叉樹稱為大根堆；相反，如果這顆完全二叉樹中任意結(jié)點(diǎn)的關(guān)鍵字小于或者等于其左孩子和右孩子的關(guān)鍵字，對應(yīng)的堆叫做小根堆。

堆排序的過程主要需要解決兩個(gè)問題：第一個(gè)是，按照堆定義建初堆；第二個(gè)是，去掉最大元后重建堆，得到次大元。

堆排序即是利用堆的特性對記錄序列進(jìn)行排序,過程如下：

1、對給定序列建堆；
2、輸出堆頂；(首元素與尾元素交換)
3、對剩余元素重建堆；(篩選首元素)
4、重復(fù)2，3，直至所有元素輸出。

注意：“篩選”須從第[n/2]個(gè)結(jié)點(diǎn)開始，逐層向上倒退，直到根結(jié)點(diǎn)。

算法分析：

1. 對深度為 k 的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；
2. n 個(gè)關(guān)鍵字的堆深度為  [log2n]+1, 初建堆所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為：n* [log2n];
3. 重建堆 n-1 次，所需進(jìn)行的關(guān)鍵字比較的次數(shù)不超過：(n-1)*2 [log2n ]; 

因此，堆排序在最壞情況下，其時(shí)間復(fù)雜度為O(nlog2n)，這是堆排序的最大優(yōu)點(diǎn)。

看完上述內(nèi)容，你們掌握在java項(xiàng)目中實(shí)現(xiàn)一個(gè)樹形選擇排序的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！