程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> java堆排序原理及算法實現

java堆排序原理及算法實現

編輯:關於JAVA

java堆排序原理及算法實現。本站提示廣大學習愛好者:(java堆排序原理及算法實現)文章只能為提供參考,不一定能成為您想要的結果。以下是java堆排序原理及算法實現正文


從堆排序的簡介到堆排序的算法實現等如下:

1. 簡介

  堆排序是建立在堆這種數據結構基礎上的選擇排序,是原址排序,時間復雜度O(nlogn),堆排序並不是一種穩定的排序方式。堆排序中通常使用的堆為最大堆。   

2. 堆的定義

  堆是一種數據結構,是一顆特殊的完全二叉樹,通常分為最大堆和最小堆。最大堆的定義為根結點最大,且根結點左右子樹都是最大堆;同樣,最小堆的定義為根結點最小,且根結點左右子樹均為最小堆。

  最大堆滿足其每一個父結點均大於其左右子結點,最小堆則滿足其每一個父結點均小於其左右子結點。

3. 堆排序

3.1 堆的存放

  在堆排序中,堆所表示的二叉樹並不需要使用指針的方式在計算機中存放,只需要使用數組即可,將樹的結點,從上至下,從左至右一個個放到數組中去。

   因此,如果數組的起始索引為0,對於一個結點i來說,它的父結點索引為⌊i/2⌋,它的左子結點索引為2i+1,右子結點索引為2i+2。最後一個非葉子節點就是最後一個結點的父親,如果數組長度為n,那麼其索引為⌊(n-1)/2⌋。

3.2 堆排序主要步驟

將無序序列構建成最大堆

將數組分成兩個區域,有序區和無序區,初始時創建一個整數i為數組的長度,用來劃分有序區和無序區,有序區初始為空。

將堆頂元素和最後一個無序區的元素交換,然後i-1。

調整使得所有無序區的元素重新為最大堆。

重復3,4步,直到 i = 0

3.3 堆的調整

  假設有某棵完全二叉樹,其左右子樹均為最大堆,如何調整使得該二叉樹成為最大堆呢?如果根結點大於左右子結點,那麼已經是最大堆了,無需調整。否則,交換根結點和左右子結點中較大的那個。假設交換的是左結點,那麼目前這棵完全二叉樹右子樹仍然是一個最大堆,左子樹則不一定,但是左子樹的左右子樹還是最大堆,因此不斷遞歸下去調整即可。

   因此,交換最後一個元素和堆頂元素後的調整步驟,就和上面所說的一致。而將無序序列構建成最大堆,同樣也可以運用這一點。從最後一個非葉子結點到第一個非葉子結點(根結點),對這些結點作為根結點的子樹,按順序調用一次上述描述的調整即可(每次調用時,該子樹的左右子樹必定是最大堆)。

4. 算法實現

#include <stdio.h>
void swap(int *a,int *b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}
//左右子樹都是最大堆,從上至下調整使得最大堆, root_index是要調整的樹的根節點,length是無序區的長度
void adjust(int array[],int root_index,int length) {
 int left_child = root_index*2+1;
 int right_child = left_child+1;
 int left_or_right = 0;
 if((left_child >= length && right_child >= length) || (left_child >= length && array[root_index] >= array[right_child]) ||
 (right_child >= length && array[root_index] >= array[left_child]) || (array[root_index] >= array[left_child] && array[root_index] >= array[right_child])){
  return;
 }
 else if (array[left_child] >= array[root_index] && (right_child >= length || array[left_child] >= array[right_child])) {
  left_or_right = 1;
 }
 else if (array[right_child] >= array[root_index] && (left_child >= length || array[right_child] >= array[left_child])) {
  left_or_right = 0;
 }
 if(left_or_right) {
  swap(&array[left_child],&array[root_index]);
  adjust(array,left_child,length);
 }
 else {
  swap(&array[right_child],&array[root_index]);
  adjust(array,right_child,length);  
 }
}
//heapsort主遞歸,每一次將無序區最後一個元素與堆頂元素交換,將堆頂元素加入有序區,因此有序區加1,無序區減1,無序區只剩一個元素的時候遞歸終止
void heapsort_main(int array[],int length,int last_index) {
 int i;
 if(last_index == 0)
  return;
 swap(&array[0],&array[last_index]);
 adjust(array,0,last_index);
 heapsort_main(array,length,last_index-1);
} 
//入口函數,array是待排序的數組,length是其長度
void heapsort(int array[],int length) {
 int i;
 for(i = length/2-1;i >= 0;i--) {
  adjust(array,i,length);
 }
 heapsort_main(array,length,length-1);
}
int main(int argc,char *argv[]) {
 int array[9] = {1,1,1,2,3,5,2,3,5};
 heapsort(array,9);
 int i;
 for(i = 0;i < 9;i++) {
  printf("%d ",array[i]);
 }
}

5.堆排序性質

時間復雜度O(nlogn)

空間復雜度O(1)

不穩定排序

本篇文章對堆排序所整理的內容,希望可以幫到需要的朋友

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved