第二十一章堆积树排序法

●前言

●认识排序

1.简要介绍

2.图形理解

3.算法分析

●二、案例实现

1.案例一

● 总结

前言

排序算法是我们在程序设计中经常见到和使用的一种算法，它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代，随着大数据和人工智能的发展，大型企业的数据库中有亿级的用户数据量。因此对其进行处理，排序算法也就成为了其中必不可缺的步骤之一。

认识排序

排序功能对计算机领域而言，是一项非常重要而且普遍的工作。排序中数据的移动方式可分为直接移动和逻辑移动两种方式，直接移动是直接交换存储数据的位置，而逻辑移动并不会移动数据存储的位置，仅改变指向这些数据辅助指针的值。排序通常按照数据量的多少和所使用的内存，可分为内部排序和外部排序，数据量小可以全部加载到内存来进行排序的，就称为内部排序，大部分排序属于此类。数据量大而无法一次性加载到内存中，必须借助磁带，磁盘等辅助存储器进行排序的，则称为外部排序。随着数据结构科学的进步，如今，陆续被提出的冒泡排序法，选择排序法，插入排序法，合并排序法，快速排序法，堆积排序法，希尔排序法，基数排序法，直接合并排序法等等，它们各有其特色和其应用场合。并且在算法中，我们非常关注算法程序代码的时间复杂度和空间复杂度，因为它会直接体现出我们程序代码的执行效率以及编程人员的逻辑思维等等的综合能力。当数据量相当庞大时，排序算法所花费的时间就显得相当重要，排序算法的时间复杂度可分为最好情况、最坏情况以及平均情况。另外，对于任何的排序算法都会有数据交换的操作，数据互换位置会暂时用到一个额外的空间，这也是排序算法中空间复杂度要考虑到的问题，而在排序算法中所使用的额外空间越小，它的空间复杂度就越好。

一、堆积树排序法是什么？

1.简要介绍

堆积树排序法是选择排序法的改进版，它减少了在选择排序法中的比较次数，从而提高了时间效率。堆积排序法用到了二叉树的技巧，它是利用堆积树去完成排序的。

2.图形理解

堆积树是一种特殊的二叉树，可以分为最大堆积树和最小堆积树：

最大堆积树需要满足的条件：

① 它是一棵完全二叉树

② 树根的值是堆积树中最大的

③ 所有节点的值都大于或等于它左右子节点的值

最小堆积树需要满足的条件：

① 它是一棵完全二叉树

② 树根的值是堆积树中最小的

③ 所有节点的值都小于或等于它左右子节点的值

（1）首先我们来理解如何将二叉树转化成堆积树的操作步骤。我们将下面如图所示表示数列（33,20,19,27,38,95,68,1,14）的二叉树进行转化：

将该二叉树中所有节点的值用数组存储起来，即tree[0]，tree[1]，tree[2]，tree[3]，tree[4]，tree[5]，tree[6]，tree[7]，tree[8]。

①tree[0]=33为树根，因为tree[1]=20<tree[0]，故不交换位置。

②因为tree[2]=19<tree[0]，故不交换位置。

③因为tree[3]=27>tree[1]，故交换位置。具体情况如下图所示：

④因为tree[4]=38>tree[1]，故交换位置。具体情况如下图所示：

⑤因为tree[5]=95>tree[2]，故交换位置。具体情况如下图所示：

⑥因为tree[6]=68<tree[2]，故不交换位置。

⑦再将树根tree[0]=33与其已经交换后的tree[1]=38，tree[2]=95比较，因为tree[0]<tree[1]<tree[2],所以树根与最大的交换位置。具体情况如下图所示：

⑧继续扫描树根子节点的情况，左子节点满足情况，右子节点不满足需要交换位置。因为tree[6=68]>tree[2]=33，故交换位置。且交换位置后，tree[0]=95>tree[2]=68，所以不交换。具体情况如下图所示：

⑨因为tree[7]=1<tree[3]，故不交换位置。

⑩因为tree[8]=14<tree[3]，故不交换位置，所以经过十个步骤过程，我们也就完成了由二叉树向堆积树的一个完整的转化过程。

（2）上面我们示范的是一棵最大堆积树的建立方法（从上往下建立）。堆积树并非唯一，如果从数组的最后一个元素，从下往上逐一比较也可以去建立一棵最大堆积树，并且通过堆积树排序法得到的数列大小是从大到小的。如果想从小到大排序，就必须去建立最小堆积树，方法与建立最大堆积树方法一致，只需注意表格中最小堆积树需满足的条件即可。下面我们用堆积排序法对(1)进行从大到小的排序：

①已经堆积树具体情况如下图所示：

②将95从树根删除，重新建立堆积树，如下图所示：

③将68从树根删除，重新建立堆积树，如下图所示：

④将38从树根删除，重新建立堆积树，如下图所示：

⑤将33从树根删除，重新建立堆积树，如下图所示：

⑥将27从树根删除，重新建立堆积树，如下图所示：

⑦将20从树根删除，重新建立堆积树，如下图所示：

⑧将19从树根删除，重新建立堆积树，如下图所示：

⑨将14从树根删除，重新建立堆积树，如下图所示：

⑩将1从树根删除，从而完成了最终的排序，如下图所示：

3.算法分析

①堆积树排序法在所有情况下，时间复杂度都为O( $n\log2^{n}$ )。

②堆积树排序法不是稳定排序法。

③堆积树排序法只需要一个额外的空间，空间复杂度为O(1)。

二、案例实现

1.案例一

①范例情况：用堆积树排序法对随机8个数据下的数列进行从小到大的排序。

②代码情况：

#include<iostream>
using namespace std;
#define size 9 //事先声明  数据元素+1
class tree {
public:int data[size];void showresult() {for (int i = 1; i < size; i++)cout << data[i] << " ";cout << endl;}void tree_start(int i,int len) {int j = 2 * i,temp=data[i],post=0;while (j <= len && post == 0){if (j < len) {if (data[j] < data[j + 1])    //找出大节点j++;}if(temp>=data[j]){                 //若树根较大，则结束比较过程post = 1;}else {                          //若树根较小，则继续进行比较data[j / 2] = data[j];j = 2 * j;}}data[j / 2] = temp;       //指定树根为父节点}void tree_sort_start() {for (int i = size / 2; i > 0; i--)    //建立堆积树的结点tree_start(i,size-1);cout << "原始堆积树的内容:"; showresult();for (int j = size - 2; j > 0; j--){int temp;//头尾结点继续交换temp = data[j + 1];data[j + 1] = data[1];data[1] = temp;tree_start(1,j);   //处理剩余节点}}
};
void text()
{tree t;cout << "请输入要排序的" << size-1 << "个数据" << endl;for (int i = 1; i < size; i++)cin >> t.data[i];cout << "排序前：";t.showresult();t.tree_sort_start();cout << "排序后：";t.showresult();
}
int main()
{text();
}

③结果展示：