数据结构：堆排序原理与实现

堆排序

假定有一组数据极多的数，让我们进行排序，那我们很容易想到一种经典的排序方法，冒泡排序，我们对冒泡排序的时间复杂度进行分析：

显然，冒泡排序的时间复杂度是 O(n^2)，当数据量巨大时，冒泡排序需要比较长时间才能完成排序，这在实际应用中是没有意义的。

而相比之下的堆排序时间开销则小得多。

接下来先给出堆排序的代码：

void Swap(int* child, int* parent) { 
    int tem = *child; 
    *child = *parent; 
    *parent = tem; 
} 

void DownAdjust(int* p,int size,int parent) { 
    int child = parent * 2 + 1; 
    while (child<size) { 
        if (child<size-1 && p[child + 1] < p[child])//size-1,不是size 
            ++child; 
        if (p[child] < p[parent]) { 
            Swap(&p[child], &p[parent]); // parent = child; child = parent * 2 + 1; 
        } else { 
            break; 
        } 
    } 
} 

//堆排序
void HeapSort(int* p, int size) { 
    //1.建堆 //先找到最后一个非叶子节点，然后逆序向下调整 
    for (int i = (size - 1 - 1) / 2; i >= 0; i--) { 
        DownAdjust(p, size, i); 
    } 
    //2.对堆排序 
     end = size - ; 
     (end>) { 
        Swap(&p[], &p[end]); 
        DownAdjust(p, end, ); 
        --end; 
    } 
}