Monday, May 17, 2004

 

Sorts總整理3--Heap Sort

Heap Sort的演算法和程式碼

《Heap Sort》

Algorithm :
Parent(i)
return i/2
Left(i)
return 2i
Right(i)
return 2i+1

Max-Heapify(A,i)
lLeft(i)
rRight(i)

if lheap-size[A] and A[l]>A[i]
   then largestl

   else largesti
if rheap-size[A] and A[r]>A[largest]
   then largestr

if largesti
   then exchange A[i]←→A[largest]
      Max-Heapify(A,largest)

Build-Max-Heap(A)
heap-size[A]←length[A]
for ilength[A]/2 downto 1
   do Max-Heapify(A,i)

Heapsort(A)
Build-Max-Heap(A)
for ilength[A] downto 2
   do exchange A[1]←→A[i]
      heap-size[A]←heap-size[A]-1
   Max-Heapify(A,1)

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 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

Comments: Post a Comment



<< Home