堆排序算法(选择排序改进)

时间:2022-05-01 08:19:27

首先要理解堆的含义:要么所有节点都不大于其子孩子节点数据,要么都不小于其子孩子节点数据

堆排序的核心思想:就是要满足所有节点都满足上面两点,如何完成,看下面

堆排序的步骤:

1.首先要建成一个大顶堆或者小顶堆,在建的过程中其实就是调整节点的位置,首先要从最后最后一个节点的母亲节点开始,按照堆的含义调整。为什么不是最后一个或者其他?因为要保证完整性和不必要性,所以只需从最后一个的母亲节点开始即可(下面的堆默认存在顺序结构,从索引0开始的,所以有些二叉树的特性请查阅二叉树),直至索引节点为0的节点。调整完成后即成为一个堆,但是这里的数据并没有排序好,所以下一部调整顺序。

2.从最后一个数据开始,与第一个数据进行交换,然后按照堆的含义调整第一个数据。为什么先选择最后一个数据?因为默认情况下,最后一个或者是较大或者是较小,可以满足调整要求。这时就考虑当前所有数据减去最后一个,因为这个已是最大或者是最小,不必再考虑.。直至调整没有任何数据,此时已完成排序。

具体图例不再标识,有此爱好可以参考其他书籍或者网上的介绍,下面看堆排序代码:

复制代码 代码如下:


int HeapSort(MergeType* L)
{
 int i = 0;
 if (!L->elem)
 {
  return -1;
 }

 

 //创建堆
 for (int i = L->len/2-1; i >= 0; i--)
 {
  HeapAdjust(L, i, L->len-1);
 }

 //堆排序
 for (i = L->len-1; i >= 0; i-- )
 {
  swap(L->elem[i], L->elem[0]);
  HeapAdjust(L, 0, i-1);
 }
 return 0; 
}

 

注意:
1)由于父子节点的关系,for循环第一个数据索引其实是L,len-1,但是其父母节点(i)与 当前节点(p)的关系:p = 2i+1 或者2i+2; 如果存储数据的节点第一个索引不是0而是1,这里p=2i或者p=2i+1,请参看有关书籍的证明,所以当前父母节点:i =(p-1)/ 2 = (L.len-1-1)/2 = L.len/2-1

2)由于再次调整数据的时候是从最后一个数据,所以需要交换数据swap,再进行当前顶点数据也就是第一个数据的堆调整,但是此时调整的对象只是(0~i)这些数据,其他已经排序好,所以不再需要调整

下面看一下调整代码,如下:

复制代码 代码如下:

int HeapAdjust(MergeType* L, int nPos, int nEnd)
{
 for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
 {
  if (L->elem[i] <= L->elem[i+1])
  {
   i++;
  }
  if (L->elem[nPos] >= L->elem[i])
  {
   break;
  }
  swap(L->elem[nPos], L->elem[i]);
  nPos = i;
 }
 return 0;
}

 

这里使用的是在一个层次上是数据直接交换,其实这不是必须的,因为最后才把数据放到最后的位置,所以也可以使用下面的代码,减少复制的次数

复制代码 代码如下:


int HeapAdjustEx(MergeType* L, int nPos, int nEnd)
{
 int nTempkey = L->elem[nPos];

 

 for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
 {
  if (L->elem[i] <= L->elem[i+1])//选出最大的子孩子
  {
   i++;
  }
  if (nTempkey >= L->elem[i]) //如果当前节点大于最大子孩子退出
  {
   break;
  }
  L->elem[nPos] = L->elem[i]; //否则进行数据交换
  nPos = i;
 }
 L->elem[nPos] = nTempkey;
 return 0;
}

 

这里就可以减少较多的复制操作,也就是俗称的移动操作次数;这里for循环的起始节点按照上面的推论,子节点应该为p=2i+1,所以第一个应该为2*nPos+1,对应当前要比较节点的做孩子,右孩子为2*nPos+2,也就是左孩子+1,其他请看注释。
时间复杂度:O(nlogn),分析过程暂略