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)
不穩定排序
本篇文章對堆排序所整理的內容,希望可以幫到需要的朋友