排序算法的数组实现 -- 堆排序（二）

堆排序：

[cpp]
void static Heap_ExChange(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

int Heap_Parent(int n_children)
{
return (n_children - 1) / 2;
}

int Heap_Left(int n_parent)
{
return 2 * n_parent + 1;
}

int Heap_Right(int n_parent)
{
return 2 * (n_parent + 1);
}

void static Max_Heapify(int * a, int heap_size, int n_parent)
{
int n_Max = 0;
int n_L = Heap_Left(n_parent);
int n_R = Heap_Right(n_parent);

if(n_L <= heap_size -1 && a[n_L] > a[n_parent])
n_Max = n_L;
else
n_Max = n_parent;

if(n_R <= heap_size - 1 && a[n_R] > a[n_Max])
n_Max = n_R;

if(n_Max != n_parent)
{
Heap_ExChange(a[n_Max],a[n_parent]);
Max_Heapify(a, heap_size, n_Max);
}
}

void static Build_Max_Heap(int *a, int size)
{
int heap_size = size;

for(int i = heap_size / 2 - 1; i >= 0; i--)
{
Max_Heapify(a,heap_size, i);
}
}

void Heap_Sort(int *a, int size)
{
int heap_size = size;
Build_Max_Heap(a, heap_size);

for(int i = size - 1; i >= 1; i--)
{
Heap_ExChange(a[0],a[i]);
heap_size --;
Max_Heapify(a, heap_size,0);
}

}

void static Heap_ExChange(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

int Heap_Parent(int n_children)
{
return (n_children - 1) / 2;
}

int Heap_Left(int n_parent)
{
return 2 * n_parent + 1;
}

int Heap_Right(int n_parent)
{
return 2 * (n_parent + 1);
}

void static Max_Heapify(int * a, int heap_size, int n_parent)
{
int n_Max = 0;
int n_L = Heap_Left(n_parent);
int n_R = Heap_Right(n_parent);

if(n_L <= heap_size -1 && a[n_L] > a[n_parent])
n_Max = n_L;
else
n_Max = n_parent;

if(n_R <= heap_size - 1 && a[n_R] > a[n_Max])
n_Max = n_R;

if(n_Max != n_parent)
{
Heap_ExChange(a[n_Max],a[n_parent]);
Max_Heapify(a, heap_size, n_Max);
}
}

void static Build_Max_Heap(int *a, int size)
{
int heap_size = size;

for(int i = heap_size / 2 - 1; i >= 0; i--)
{
Max_Heapify(a,heap_size, i);
}
}

void Heap_Sort(int *a, int size)
{
int heap_size = size;
Build_Max_Heap(a, heap_size);

for(int i = size - 1; i >= 1; i--)
{
Heap_ExChange(a[0],a[i]);
heap_size --;
Max_Heapify(a, heap_size,0);
}

}

作者：wchm_seu