首頁 >Java >java教程 >java資料結構排序演算法（1）樹形選擇排序

java資料結構排序演算法（1）樹形選擇排序

零下一度原創: 2017-05-31 09:27:522404瀏覽

這篇文章主要介紹了java資料結構排序演算法之樹形選擇排序,結合具體實例形式分析了java樹形選擇排序的原理、實現技巧與相關注意事項,需要的朋友可以參考下

本文實例講述了java資料結構排序演算法之樹形選擇排序。分享給大家供大家參考，具體如下：

這裡我們就來說說選擇類別排序之一的排序：樹狀選擇排序

在簡單選擇排序中，每次的比較都沒有用到上次比較的結果，所以比較操作的時間複雜度是O(N^2)，想要降低比較的次數，則需要把比較過程中的大小關係保存下來。樹狀選擇排序是對簡單選擇排序的改進。

樹形選擇排序：又稱錦標賽排序（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]個結點開始，逐層向上倒退，直到根結點。