堆排序前三趟的序列状态,堆排序每一趟例题
堆排序过程
1，实用的排序算法：选择排序
（1）选择排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在后面n-i个待排序元素中选择排序码最小的元素，作为有序元素序列的第i个元素。待到第n-2趟做完，待排序元素只剩下一个，就不用再选了。
（2）三种常用的选择排序方法
1直接选择排序
2锦标赛排序
3堆排序
其中，直接排序的思路和实现都比较简单，并且相比其他排序算法，直接选择排序有一个突出的优势——数据的移动次数少。
（3）直接选择排序简介
1直接选择排序（select sort）是一种简单的排序方法，它的基本步骤是：
1）在一组元素V[i]~V[n-1]中选择具有最小排序码的元素；
2）若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素对调；
3）在这组元素中剔除这个具有最小排序码的元素，在剩下的元素V[i+1]~V[n-1]中重复执行1、2步骤，直到剩余元素只有一个为止。
2直接选择排序使用注意
它对一类重要的元素序列具有较好的效率，这就是元素规模很大，而排序码却比较小的序列。因为对这种序列进行排序，移动操作所花费的时间要比比较操作的时间大的多，而其他算法移动操作的次数都要比直接选择排序来的多，直接选择排序是一种不稳定的 排序方法。
3直接选择排序C++函数代码
//函数功能，直接选择排序算法对数列排序
//函数参数，数列起点，数列终点
void dselect_sort(const int start, const int end) {
for (int i = start; i end; ++i) {
int min_position = i;
for (int j = i + 1; j = end; ++j) { //此循环用来寻找最小关键码
if (numbers[j] numbers[min_position]) {
min_position = j;
}
}
if (min_position != i) { //避免自己与自己交换
swap(numbers[min_position], numbers[i]);
（4）关于锦标赛排序
直接选择排序中，当n比较大时，排序码的比较次数相当多，这是因为在后一趟比较选择时，往往把前一趟已经做过的比较又重复了一遍，没有把前一趟的比较结果保留下来。
锦标赛排序（tournament sort）克服了这一缺点。它的思想与体育比赛类似，就是把待排序元素两两进行竞赛，选出其中的胜利者，之后胜利者之间继续竞赛，再选出其中的胜利者，然后重复这一过程，最终构造出胜者树，从而实现排序的目的。
2，堆排序的排序过程
（1）个人理解：堆排序是选择排序的一种，所以它也符合选择排序的整体思想。直接选择排序是在还未成序的元素中逐个比较选择，而堆排序是首先建立一个堆（最大堆或最小堆），这使得数列已经“大致”成序，之后只需要局部调整来重建堆即可。建立堆及重建堆这一过程映射到数组中，其实就是一个选择的过程，只不过不是逐个比较选择，而是借助完全二叉树来做到有目的的比较选择。这也是堆排序性能优于直接选择排序的一个体现。
（2）堆排序分为两个步骤：
1根据初始输入数据，利用堆的调整算法形成初始堆；
2通过一系列的元素交换和重新调整堆进行排序。
（3）堆排序的排序思路
1前提，我们是要对n个数据进行递增排序，也就是说拥有最大排序码的元素应该在数组的末端。
2首先建立一个最大堆，则堆的第一个元素heap[0]具有最大的排序码，将heap[0]与heap[n-1]对调，把具有最大排序码的元素交换到最后，再对前面n-1个元素，使用堆的调整算法siftDown(0,n-2)，重新建立最大堆。结果具有次最大排序码的元素又浮到堆顶，即heap[0]的位置，再对调heap[0]与heap[n-2]，并调用siftDown(0，n-3)，对前n-2个元素重新调整，……如此反复，最后得到一个数列的排序码递增序列。
（4）堆排序的排序过程：
下面给出局部调整成最大堆的函数实现siftDown()，这个函数在前面最小堆实现博文中的实现思路已经给出，只需做微小的调整即可用在这里建立最大堆。
排序算法的各趟排序算法
以关键字序列( )为例 分别写出执行以下排序算法的各趟排序结束时 关键字序列的状态
( ) 直接插入排序 ( )希尔排序 ( )冒泡排序 ( )快速排序
( ) 直接选择排序 ( ) 堆排序 ( ) 归并排序 ( )基数排序
上述方法中 哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例
答 ( )直接插入排序:(方括号表示无序区)
初始态: [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟 [ ]
第七趟 [ ]
第八趟 [ ]
第九趟
( )希尔排序(增量为 )
初始态:
第一趟
第二趟
第三趟
( )冒泡排序(方括号为无序区)
初始态 [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟
( )快速排序 (方括号表示无序区 层表示对应的递归树的层数)
初始态 [ ]
第二层 [ ] [ ]
第三层 [ ] [ ] [ ]
第四层 [ ] [ ] [ ]
第五层 [ ]
第六层
( )直接选择排序 (方括号为无序区)
初始态 [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟 [ ]
第七趟 [ ]
第八趟 [ ]
第九趟
( )堆排序 (通过画二*树可以一步步得出排序结果)
初始态 [ ]
建立初始堆 [ ]
第一次排序重建堆 [ ]
第二次排序重建堆 [ ]
第三次排序重建堆 [ ]
第四次排序重建堆 [ ]
第五次排序重建堆 [ ]
第六次排序重建堆 [ ]
第七次排序重建堆 [ ]
第八次排序重建堆 [ ]
第九次排序重建堆
( )归并排序(为了表示方便 采用自底向上的归并 方括号为有序区)
初始态 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
第一趟 [ ] [ ] [ ] [ ] [ ]
第二趟 [ ] [ ] [ ]
第三趟 [ ] [ ]
第四趟 [ ]
( )基数排序(方括号内表示一个箱子共有 个箱子 箱号从 到 )
初始态
第一趟 [] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
第二趟 [ ] [] [ ] [ ] [ ] [ ] [ ] [ ] [] [ ]
第三趟 [ ] [ ] [ ] [ ] [ ] [] [ ] [ ] [ ] [ ]
在上面的排序方法中 直接插入排序 冒泡排序 归并排序和基数排序是稳定的 其他排序算法均是不稳定的 现举实例如下 以带*号的表示区别
希尔排序 [ * ]
快速排序 [ * ]
直接选择排序 [ * ]
lishixinzhi/Article/program/sjjg/201311/23531
小根堆的建立
构建的初始堆: 7 13 26 14 18 45 60 32
第一趟重建堆之后序列状态：13 14 26 32 18 45 60 7
第二趟重建堆之后序列状态：14 18 26 32 60 45 13 7
数据结构堆排序
首先建立初始大根堆：(99,95,60,38,76,10,40)
第一趟排序后结果：(95,76,60,38,40,10,99)
第二趟排序后结果：(76,40,60,38,10,95,99)
第三趟排序后结果：(60,40,10,38,76,95,99)
第四趟排序后结果：(40,38,10,60,76,95,99)
第五趟排序后结果：(38,10,40,60,76,95,99)
第六趟排序后结果：(10,38,40,60,76,95,99)
用堆排序方法给关键字序列进行排序，急急！！
首先依次输入关键字，建立堆，此时在数组的排列为
：2 10 13 15 12 14，
之后便开始每次取最小值放在堆尾，并跟新堆，每步结果依次为
：10 12 13 15 14 2
：12 14 13 15 10 2
：13 14 15 12 10 2
：14 15 13 12 10 2
：15 14 13 12 10 2
