堆排的原理和结构:
堆排序是一种常见的排序算法,基于堆这种数据结构实现。堆是一种特殊的树形数据结构,它满足以下两个条件:
堆是一棵完全二叉树。
堆的任意节点的值,都必须大于等于(或小于等于)左右子节点的值。
根据这些定义,我们可以将堆分为两种类型:最大堆和最小堆。
最大堆:根节点的值最大,任意节点的值都大于等于其左右子节点的值。
最小堆:根节点的值最小,任意节点的值都小于等于其左右子节点的值。
堆排序分为两个步骤:建堆和排序。
建堆:将待排序元素序列构建为一个堆。具体操作是从后往前遍历所有非叶子节点,逐个调整节点的值,使得它成为一个符合堆的定义的结构。建堆操作时间复杂度为O(n)。
排序:将堆中的元素依次取出,形成有序序列。具体的操作是,将堆顶元素(最大值或最小值)与堆底元素交换,然后将剩余元素重新构建堆。排序操作时间复杂度为O(n*log n)。
因此,堆排序的时间复杂度为O(n*log n),是一种不稳定的排序算法。
data++是什么意思(data)是一个数组?
data++是C语言中的一个表达式,它会将指针data指向的地址向后移动一个存储单位的距离,这里一个存储单位指的是数组的元素大小。如果data是一个数组名,则它代表数组的首元素的地址。
例如,如果data是一个int类型的数组,其大小为 4 字节,那么 data++ 表示将指针data向右移动 4 字节,指向数组中下一个元素的地址。
需要注意的是,由于data是一个指向数组的指针,当使用data++表达式时,会改变指针指向的位置,因此建议在代码中使用时要小心。
当传入一个数组时,这个数组的指针指向哪里?
在C语言中,当使用一个数组名作为实参传递给函数时,实际传递的是数组的第一个元素的地址,即数组名会被转换为一个指向其第一个元素的指针.
void headvisit(int data[],int n)
{
int i , j , t;
while(n>1) //共有n个元素,每一个都要与父节点的值相比较
{
for(i=n/2;i>=1;i--)// n/2是找到最后一个叶子的父节点在树中的位置,当i=1时,就说明此时在根节点处,在树中根节点是从1开始的 并不是0
{
if(data[i-1]>data[2*i-1]) //根据树的基本结构 此处是与左孩子比较
{
t = data[2*i-1];
data[2*i-1] = data[i-1];
data[i-1] = t;
}
//先判断右孩子是否存在 右孩子的度一定是小于等于总节点数的(n)
if( 2*i+1 <= n && data[i-1] > data[2*i-1+1])
{
t = data[2*i-1+1];
data[2*i-1+1] = data[i-1];
data[i-1] = t;
}
}
data++;
n--;
}
}
void outs(int data[],int n)
{
for(int i = 0 ; i < n ; i++)
{
printf("%10d",data[i]);
}
}
int main()
{
int data[5] = {9,25,444,17536,9456};
headvisit(data,5);
outs(data,5);
return 0;
}