首页 > 代码库 > 堆排序算法

堆排序算法

2024-08-08 02:56:14   223人阅读

/* date:2014.12.15
堆结构：是一种树结构，准确说为完全二叉树。在这个树中，每个节点对应原始数据的一个记录，且满足一下条件：1.如果按照从小到大的顺序排序，要求非叶节点的数据要大于或等于其左右子节点的数据；2.如果按照从大到小的顺序排序，要求非叶节点的数据要小于或等于其左右子节点的数据。
堆排序思路：基于选择排序的思想，利用堆结构和二叉树的一些性质来完成数据的排序。
流程：1).构造堆结构，把原始的无序数据按前面堆结构的定义进行调序；
            2).堆排序输出。
时间复杂度：最差O(nlog2(n))，平均O(nlog2(n)).
空间复杂度：O(1).
是一种 不稳定 的排序算法.

*/ 


void HeapSort(int *arr,int n)

{
int i,j,h,k,temp;


for (i = (n / 2) - 1;i >= 0;i --)
{
while (2 * i + 1 < n)
{
j = 2 * i + 1;
if ((j + 1) < n)
{
if (arr[j] < arr[j + 1])
{
j ++;
}
}
if (arr[i] < arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i = j;
} 
else
{
break;
}
}

}


printf("初始化为大顶堆为：");

for (h = 0;h < n;h ++)
{
printf("%d ",arr[h]);
}
printf("\n");

for (i = n - 1;i > 0;i --)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
k = 0;
while (2 * k + 1 < i)
{
j = 2 * k + 1;
if ((j + 1) < i)
{
if (arr[j] < arr[j + 1])
{
j ++;
}
}
if (arr[k] < arr[j])
{
temp = arr[k];
arr[k] = arr[j];
arr[j] = temp;
k = j;
} 
else
{
break;
}
}

printf("第 %d 次排序结果为：",n - i);
for (h = 0;h < n;h ++)
{
printf("%d ",arr[h]);
}
printf("\n");
}

}



堆排序算法


联系
我们