堆排序法，堆排序怎么排

123

堆排序法
请高人讲解一下堆排序法到底是怎么排的，属于计算机二级的中的排序问题，能不能附加例题呢



堆排序法，就是通过堆这种数据结构来实现排序，算法复杂度为O(nlogn)。
堆是一种完全二叉树且所有的父节点均大于（或小于）其子节点。
堆排序就是将所有待排序的元素组成一个堆，然后不断弹出堆顶的元素并调用函数维持堆序，直到所有元素均被弹出后，排序完成。被弹出的元素序列即一个有序数列。

维持堆序的一般做法是这样：

当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止）

当一个根节点被弹出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。

以下是我自己写的一个C++的堆排序的程序，希望对你理解该算法有帮助。

#include<iostream>
using namespace std;
int heap[10000],size;
void Percup(int s)
{
    if(s==1)
        return ;
    if(heap[s/2]<heap)
    {
        swap(heap[s

堆排序如何排
对（541，132，984，746，518，181，946，314，205，827）进行从大到小排序，用快速排序（以中间元素518为基准），第一趟扫描结果是？写出每一步的步骤。



下面的那个链接已经死链了，看下堆排序求topK吧：
这个你得先看看堆排序的实现原理



数据结构中常见的排序方式都有哪些？比如冒泡排序，快速排序等。每种排序具体是怎么排的？
我找到了这几种，谁可以说下具体是如何排序的。1、插入排序（直接插入排序和希尔排序）2、选择排序（直接选择排序和堆排序）3、交换排序（冒泡排序和快速排序）4、归并排序5、基数排序



1.直接插入：就是有一个已经排好的子序列，它是有序的。然后来一个插入一个仍是这个序列有序。比如a1本身就是有序的。a2来了，要和a1比较，a2大就插在a1之后，小就在a1之前，那么a1、a2就是新的有序子序列，然后a3来了，又要插入进来，逐个与a2、a1比较插在它的适当位置再次形成子序列，就按这样一步步进行，知道最后一个插入时，以前的都已经有序了。
2.希尔排序：由于有时候数据量大，用直接插入就不太合适。于是把你的一组待排序数据按如8、4、2、1的一组增量数来分组，即第一次，a1和a9和a17甚至还有更多间隔为八的数分为一组进行直接插入排序，第二次则是新的a1和a5、a9、a13……依次知道最后比较数据之间的间隔数为1，每次都进行插入排序
3.直接选择：n个数逐个比较，谁大的谁放最后（n的位置），比较范围减一；然后又从n-1个数中找最大的，又放最后（n-1的位置），依次这样进行就可以。
4.冒泡：比较的时候如果前者比后者大就要进行值的交换。那么最大的每次都会沉到底下。比较范围减一。
5、快速排序：要采用分划控制。比较复杂。


数据结构的排序方法有哪些？


冒泡排序，快速排序，堆排序。