堆排序

堆排序是另一種選擇排序方法,它是樹型選擇排序的改進,它使用的輔助空間較少,僅需要一個元素用于空間交換。

堆:根結(jié)點的關(guān)鍵碼值或者大于左右子樹或者都小于左右子樹,而且左右子樹也是堆。

如果每個結(jié)點的值都大于左右子樹關(guān)鍵碼值,稱之為大頂堆。每個結(jié)點的值都小于左右子樹的關(guān)鍵碼值,稱之為小頂堆。

首先,堆是一個完全二叉樹。堆排序包含兩個過程:

(1)初建堆

(2)調(diào)整堆

調(diào)整堆:對于第二個過程,描述如下,第一次,取出堆頂元素與R[n]進行交換,然后從根結(jié)點開始調(diào)整堆,根結(jié)點與左右孩子中較大者交換,這樣，左右子樹的堆會被破壞,繼續(xù)進行上述操作,直到葉子結(jié)點為止。第二次,取出堆頂元素與R[n-1]交換,然后調(diào)整堆。

初建堆:從非終端結(jié)點開始一直到根結(jié)點,執(zhí)行調(diào)整堆的過程。這樣,就會建立一個大頂堆。

如果排序過程中,是按照從小到大正序,那么建立一個大頂堆。如果是逆序就建立一個小頂堆。

堆排序算法的JAVA實現(xiàn):

/**
 * 堆排序包括兩個步驟 (1)初始堆(堆的定義：(1)堆是一個完全二叉樹(2)根結(jié)點的值或者大于左右子樹的值或者小于左右子樹的值(3)左右子樹也是一個堆)
 * (2)調(diào)整堆(當初始小頂堆之后，堆頂元素是最小的元素，取出最小的元素與最后一個元素相交換，再把剩下n-1個元素調(diào)整成堆,依次調(diào)整直到1為止)
 * 非終端節(jié)點調(diào)整 初始堆時從n/2向上調(diào)整成堆 把第一個元素與最后一個元素交換之后從第1個元素開始調(diào)整成新堆
 *
 * @author Administrator
 *
 */
public class HeapSort {
 public static void main(String[] args) {
  int num[] = new int[] { 0, 5, 40, 32, 2, 2221 };
  heapsort(num, 5);
  for (int x = 0; x < num.length - 1; x++) {
   System.out.print(num[x + 1] + " ");
  }
 }

//調(diào)整堆

 public static void adjustHeap(int[] num, int s, int t) {

  int i = s;
  int x = num[s];
  for (int j = 2 * i; j <= t; j = 2 * j) {
   if (j < t && num[j] < num[j + 1])
    j = j + 1;// 找出較大者把較大者給num[i]
   if (x > num[j])
    break;
   num[i] = num[j];
   i = j;

  }

  num[i] = x;

 }

 public static void heapsort(int[] num, int n) {
  // 初始建堆從n/2開始向根調(diào)整

  int i;
  for (i = n / 2; i >= 1; i--) {

   adjustHeap(num, i, n);//初始堆過程
  }

  for (i = n; i > 1; i--) {
   num[0] = num[i];// 將堆頂元素與第n,n-1,.....2個元素相交換
   num[i] = num[1];
   num[1] = num[0];// 從num[1]到num[i-1]調(diào)整成新堆
   adjustHeap(num, 1, i - 1);

  }

 }

}

性能分析:

時間復雜度:

堆是一個完全二叉樹,設(shè)樹高為k=log2n+1,從根到葉的調(diào)整,關(guān)鍵碼比較的次數(shù)為2(k-1)，交換的次數(shù)至多為k次。所以比較的次數(shù)不超過

2*(log2(n-1)+log2(n-2)+....+log22)<2nlog2n

而比較的次數(shù)不超過4n.所以堆排序的時間復雜度為O(nlogn).

空間復雜度:

需要一個單元的輔助空間用于交換,所以輔助空間為O(1).

穩(wěn)定性:

堆排序調(diào)整過程中存在著交換,所以堆排序是一個不穩(wěn)定的排序算法。

堆排序的實例過程可以參考http://blog.sina.com.cn/s/blog_534408920100acqv.html.