排序算法的数组实现 -- 堆排序(二)
堆排序:
[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
补充:软件开发 , C++ ,