堆排序（包含最大堆和最小堆）

堆排序 時間複雜度nlgn，原址排序。

通用函數

int parent(int i)
{
    return (i - 1) >> 1;
}
int left(int i)
{
    return (i << 1) + 1;
}
int right(int i)
{
    return (i << 1) + 2;
}
           

最大堆排序

void max_heapify(int *array,int heap_size,int parent_index)
{
    int l = left(parent_index);
    int r = right(parent_index);
    int largest = parent_index;
    if(l < heap_size && array[l] > array[parent_index])
        largest = l;
    if(r < heap_size && array[r] > array[largest])
        largest = r;
    if(largest != parent_index)
    {
        int temp = array[largest];
        array[largest] = array[parent_index];
        array[parent_index] = temp;
        max_heapify(array,heap_size,largest);
    }
}
void build_heap(int *array,int length)
{
    for (int i = length/2; i >= 0 ; i--) {
        max_heapify(array,length,i);
    }
}
void heap_sort(int *array,int length)
{
    build_heap(array,length);
    for (int i = length - 1; i > 0 ; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        max_heapify(array,i,0);
    }
}
           

最小堆排序

void min_heapify(int *array,int heap_size,int parent_index)
{
    int l = left(parent_index);
    int r = right(parent_index);
    int smallest = parent_index;
    if(l < heap_size && array[l] < array[smallest])
        smallest = l;
    if(r < heap_size && array[r] < array[smallest])
    {
        smallest = r;
    }
    if(smallest != parent_index)
    {
        int temp = array[smallest];
        array[smallest] = array[parent_index];
        array[parent_index] = temp;
        min_heapify(array,heap_size,smallest);
    }
}
void build_min_heap(int *array,int length)
{
    for (int i = length/2; i >= 0 ; i--) {
        min_heapify(array,length,i);
    }
}
void min_heap_sort(int *array,int length)
{
    build_min_heap(array,length);
    for (int i = length - 1; i > 0 ; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        min_heapify(array,i,0);
    }
}