ヒープソートC++
1111 ワード
#include <iostream>
using namespace std;
void AdjustHeap(int A[], int hlen, int i){
int left = 2*(i+1)-1;
int right = 2*(i+1);
int largest = i;
int temp;
while(left < hlen || right < hlen){
if(left < hlen && A[largest] < A[left])
largest = left;
if(right < hlen && A[largest] < A[right])
largest = right;
if( i != largest) //
{
temp = A[largest];
A[largest] = A[i];
A[i] = temp;
i = largest; // ,
left = 2*(i+1)-1;
right = 2*(i+1);
}else
break; //
}
}
void BuildHeap(int A[], int hlen){
int i;
int begin = hlen/2 -1;
for(i=begin; i>=0; i--)
AdjustHeap(A, hlen, i);
}
void HeapSort(int A[], int alen){
int hlen = alen;
int temp;
BuildHeap(A, hlen);
while(hlen > 1){
temp = A[hlen -1]; //
A[hlen - 1] = A[0];
A[0] = temp;
hlen--; //
AdjustHeap(A, hlen, 0); //
}
}
int main() {
int arr[5] = {6,2,4,1,5};
HeapSort(arr,5);
for(int i=0; i<5; i++)
cout << arr[i] << " ";
return 0;
}