排序算法的數組實現 -- 堆排序（二）

堆排序：

[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