堆排序算法(选择排序改进)
首先要理解堆的含义：要么所有节点都不大于其子孩子节点数据，要么都不小于其子孩子节点数据
堆排序的核心思想：就是要满足所有节点都满足上面两点，如何完成，看下面
堆排序的步骤：
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），分析过程暂略
相关文章
- 这篇文章主要介绍了VC++实现选择排序算法简单示例,代码简洁易懂,有助于读者对数据结构与算法的学习,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++选择排序算法实例,本文先是介绍了什么是选择排序,然后给出了实现代码,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了堆排序算法(选择排序改进)，有需要的朋友可以参考一下...2020-04-25
- 本篇文章是对使用c语言实现冒泡排序,选择排序,快速排序的代码进行了详细的分析介绍，需要的朋友参考下...2020-04-25
- 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从无序组的数据元素中选出最小（或最大）的一个元素，存放在无序组的起始位置，无序组元素减少，有序组元素增加，直到全部待排序的数据元素排完。...2020-04-25
- 这篇文章主要介绍了java数组算法例题代码详解(冒泡排序,选择排序),本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-07-16
- 本篇文章主要介绍了 C语言选择排序算法,这里提供代码实例以便大家理解,通过本文,更好的理解排序算法...2020-04-25
- 这篇文章主要为大家详细介绍了C++选择排序算法实例，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2020-04-25
- 大家好，本篇文章主要讲的是C++递归实现选择排序算法，感兴趣的同学赶快来看一看吧对你有帮助的话记得收藏一下，方便下次浏览...2021-12-31