排序算法总结?常用的排序算法分析?排序算法 java?堆排序算法 总结

你是否正在寻找关于排序算法总结的内容？让我把最棒的东西奉献给你：

最近面试，老是被问到堆排序算法。
回答时老是感觉思路不清楚，现在总结一下，把思路弄清楚的。

1.堆排序是利用堆的特性对记录序列进行排序的一种排序方法。
好的那么堆得特性是什么呢？
堆得定义：

堆是满足下列性质的数列{r1, r2, …，rn}：

如下图最开始是一个小顶堆。当把97和13 交换后不是堆了，所以我们要调整根节点使之成为堆即筛选。(注意:是自堆顶到叶子的筛选过程，应该刚开始是堆由于把堆顶给换了，罪魁祸首是堆顶，其它小范围还是堆，所以是从堆顶开始)。

这其中还要注意一点。97 与13 交换后应该跟27 比较为什么呢？
1.因为是小顶堆，所以在97 的子节点里选择小者。如果把38放上去。38成了27的父节点比27大就不是小顶堆了，。如果换成大顶堆就要比较把大的数据放上去。
所以程序里交换时要先要比较一下。
程序如下：
//堆调整算法 void HeapAdjust (HeapType &H, int s, int m) { // 已知 H.r[s..m]中记录的关键字除 H.r[s] 之外 //均满足堆的特征，本函数自上而下调整 H.r[s] //的关键字，使 H.r[s..m] 也成为一个大顶堆 rc = H.r[s]; // 暂存 H.r[s] for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 自上而下的筛选过程; } // 自上而下的筛选过程 if ( j<m && H.r[j].key>H.r[j+1].key ) ++j; // 左/右“子树根”之间先进行相互比较 // 令 j 指示关键字较小记录的位置 if ( rc.key <= H.r[j].key ) break; // 再作“根”和“子树根”之间的比较， // 若“>=”成立，则说明已找到 rc 的插 // 入位置 s ，不需要继续往下调整 H.r[s] = H.r[j]; s = j; // 否则记录上移，尚需继续往下调整 H.r[s] = rc; // 将调整前的堆顶记录插入到 s (注意插入的位置为s j=2*s) } // HeapAdjust

如下图建堆过程： 从97 开始->65->38 ->49这是从下往上(大范围从下往上)。第二个图到65时又 65与13 调整了(从上往下调整)。当到49时也是49<-> 13 <-> 27所以也是从上之下调整(为了确保加入该结点后还是堆)。

程序如下：
堆排序算法如下：
void HeapSort ( HeapType &H ) { // 对顺序表 H 进行堆排序 for ( i=H.length/2; i>0; --i ) HeapAdjust ( H.r, i, H.length ); // 建小顶堆 for ( i=H.length; i>1; --i ) { H.r[1]←→H.r[i]; // 将堆顶记录和当前未经排序子序列 // H.r[1..i]中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选 } } // HeapSort
note： 堆排序算法以前看过几遍老是忘，问得时候思路不太清晰。只要把关键几个点弄清楚，把思路搞清楚了以后就不怕了。

以上就是关于排序算法总结的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/shenmilingyu/article-18190-1.html