Monday, May 17, 2004
Sorts總整理3--Heap Sort
Heap Sort的演算法和程式碼
《Heap Sort》
Algorithm : Parent(i)
java code:整數排序
return └i/2┘Left(i)
return 2iRight(i)
return 2i+1Max-Heapify(A,i)
l←Left(i) r←Right(i) if l≦heap-size[A] and A[l]>A[i] then largest←l else largest←i if r≦heap-size[A] and A[r]>A[largest] then largest←r if largest≠i then exchange A[i]←→A[largest] Max-Heapify(A,largest)Build-Max-Heap(A)
heap-size[A]←length[A]
for i←└length[A]/2┘ downto 1
do Max-Heapify(A,i)
Heapsort(A)
Build-Max-Heap(A) for i ←length[A] downto 2 do exchange A[1]←→A[i] heap-size[A]←heap-size[A]-1 Max-Heapify(A,1)
int parent(int i){ return (i - 1)/2; } int left(int i){ return 2 * i + 1; } int right(int i){ return 2 * i + 2; } void heapSort(int[] Array){ buildMaxHeap( Array ); for(int i = Array.length - 1; i >= 1; i--){ int temp = Array[0]; Array[0] = Array[i]; Array[i] = temp; heapSize--; maxHeapify(Array, 0); } } void buildMaxHeap(int[] Array){ heapSize = Array.length; for(int i = (int)( (Array.length/2) - 1 ); i >= 0; i--){ maxHeapify(Array, i); } } void maxHeapify(int[] Array, int i){ int L = left(i); int R = right(i); int largest; if( (L < heapSize) && (Array[L] > Array[i]) ) largest = L; else largest = i; if( (R < heapSize) && (Array[R] > Array[largest]) ) largest = R; if(largest != i){ int temp = Array[i]; Array[i] = Array[largest]; Array[largest] = temp; maxHeapify(Array, largest); } }java code:字串排序
int parent(int i){ return (i - 1)/2; } int left(int i){ return 2 * i + 1; } int right(int i){ return 2 * i + 2; } void buildMaxHeap(String[] Array) { heapSize = Array.length; for (int i = (int) ((Array.length / 2) - 1); i >= 0; i--) { maxHeapify(Array, i); } } void maxHeapify(String[] Array, int i) { int L = left(i); int R = right(i); int largest; if ((L < heapSize) && (Array[L].name.compareTo(Array[i].name) > 0)) { largest = L; } else { largest = i; } if ((R < heapSize) && (Array[R].name.compareTo(Array[largest].name) > 0)) { largest = R; } if (largest != i) { String temp = Array[i].name; Array[i].name = Array[largest].name; Array[largest].name = temp; maxHeapify(Array, largest); } } void heapSort(String[] Array) { buildMaxHeap(Array); for (int i = Array.length - 1; i >= 1; i--) { String temp = Array[0].name; Array[0].name = Array[i].name; Array[i].name = temp; heapSize--; maxHeapify(Array, 0); } }由 shumi 發表於 May 17, 2004 12:23 AM