排序算法—-堆排序

花了一晚上时间研究堆排序,这个排序困扰了哥很久,终于搞清楚了。

一、堆的定义

1.   父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值;

2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

 

二、已知结点 i ,则它的子结点 为2*i+1 与 2*i+2 ;父节点为(i-1)/2 ;

 

三、堆排序

堆排序分为几个部分;

1.初始化堆; 2.输出堆顶元素 ; 3.使用最后一个元素替代堆顶元素,调整堆,循环输出;

 

调整结点i ,使之成为大根堆或者小根堆,算法如下:

//  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
void AdjustHeap (int a[ ], int i, int n)
{
int j, temp;

temp = a[i];
j = 2 * i + 1;  //左孩子下标
while (j < n)  //向下调整,判断是否为叶子结点,调整是否结束
{
if (j + 1 < n && a[j + 1] < a[j]) //若右孩子存在,找出左右孩子最小的;否则 ,在左孩子最小
j++;

if (a[j] >= temp)
break;

a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点
i = j;       //循环,继续向下调整
j = 2 * i + 1;
}
a[i] = temp;

堆的存储一般是线性数组;调整堆时从第一个不是叶子节点的非终端结点,即(n-1)/2开始,开始向下调整;

初始化堆的算法:

  /*
输入:数组A,堆的大小n
功能:建堆
*/
void BuildHeap(int a[ ], int n)
{
int i;
int begin = n/2 – 1;  //最后一个非叶子节点
for (i = begin; i >= 0; i–){
AdjustHeap(A, n, i);  

        }
}

 

堆排序 就是将堆顶元素输出(分大根堆或者小根堆),然后堆进行调整,循环输出;算法如下:

void HeapSort(int a[ ], int n)
{

while (n > 1)    {

            temp = a[n-1];    //交换堆的第一个元素和堆的最后一个元素
a[n-1] = a[0];
a[0] = temp;
n–;        //堆的大小减一
AdjustHeap(A, n, 0);  //调堆

for( int i = 0 ;i <n; i++)

printf(“%d  “,a[i]);//输出排序后的数组
}

}

接下来分析下算法时间的复杂度:

初始化堆的时候:O(n)  是个复杂的公式推导,有兴趣可以自行推导

调整堆的时候:O(logn),循环调堆 复杂度:O(nlogn)

因此最好或者最坏情况下,堆排序的运行时间都是O(nlogn)

标签