Java笔试问题回顾2

文章目录

• 解析XML时，需要校验节点是否闭合
• • 栈
• 数据库连接
• • 外部连接
  • 内部连接
• 事务隔离级别
• • 更新丢失
  • 脏读
  • 不可重复读
  • 标准SQL规范中，定义了4个事务隔离级别，不同的隔离级别对事务的处理不同。
  • 未授权读取
  • 授权读取
  • 可重复读取（Repeatable Read）
  • 序列化（Serializable）
• 内存保护
• 传输层协议
• • TCP协议
  • • 三次握手
    • 四次断开
  • UDP协议
• 排序算法
• • 外部排序
  • • 多路归并排序
  • 内排序
  • • 冒泡排序
    • • 原理
      • 时间复杂度
      • 稳定性
      • 代码
      • 优化
    • 快速排序（Quicksort）
    • • 原理
      • 时间复杂度
    • 选择排序
    • • 时间复杂度
      • 稳定性
    • 插入排序
    • • 代码
      • 时间复杂度
      • 稳定性
    • 希尔排序
    • • 代码
    • 归并排序
    • • 代码
      • 效率和稳定性
    • 堆排序
    • • 代码

解析XML时，需要校验节点是否闭合

栈的应用：
1、符号匹配；
2、表达式求值；
3、实现函数调用，由其是递归
栈的常见应用：浏览器历史纪录，Android中的最近任务，Activity的启动模式，CPU中栈的实现，Word自动保存，解析计算式，解析xml/json
节点闭合的话，有头尾符号相对应，遇到头符号将其放入栈中，遇到尾符号时，弹出栈的内容，看是否有与之对应的头符号，栈的特性刚好符合符号匹配的就近原则。
鉴于XML的标签是成对出现的，所以为了检验成对性，需要与后一个相比较，那也就是数据结构中所谓的：后进先出，也就是栈

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。
栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：
1．函数的返回地址和参数
2．临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。

数据库连接 外部连接

外连接分为左外连接、右外连接和全外连接三种连接方式（左外连接即LEFT OUTER JOIN；右外连接即RIGHT OUTER JOIN）。
左连接显示JION左表的行，右表没有想匹配的，用NUL代替！右联接和左连接相反，全连接和左右连接的合计。

 LEFT JOIN: 即使右表中没有匹配，也从左表返回所有的行
   从左表返回所有的行的意思是在匹配完正确的结果后，如果左表中还有一些没有匹配的数据，也会将这些数据输出。左表中的数据会被完全匹配，即使右表中没有数据和它对应，如果是这种情况，就用null补充右表中的数据。
   比如要选择左表.姓,左表.名,右表.性别
   如果条件语句没有配置成功，左表中剩下的那些依旧要输出（会按序输出在正确结果的下方），并且性别为空（因为没有匹配成功，性别是右表的属性）
 RIGHT JOIN: 即使左表中没有匹配，也从右表返回所有的行
   从右表返回所有的行和LEFT JOIN相反。右表中的数据会被完全匹配，即使左表中没有数据和它对应，如果是这种情况，就用null补充左表中的数据。
 FULL JOIN: 只要其中一个表中存在匹配，就返回行
   FULL JOIN就是在正确的结果基础上，把左表和右表（ LEFT JOIN和RIGHT JOIN的结果都放在正确结果下方）。
   两个表中的数据都会被完全匹配出来，如果另外一个表中没有数据与它对应，那就显示null进行匹配，MySQL数据库不支持这种写法。

内部连接

只有满足连接条件的记录才会被包含在查询结果中，inner可以省略，也就是说我们用的join都是内连接。

 INNER JOIN（内连接）：在表中存在至少一个匹配时，返回行。

事务隔离级别

在数据库操作中，为了有效保证并发读取数据的正确性，提出的事务隔离级别。

更新丢失

两个事务都同时更新一行数据，一个事务对数据的更新把另一个事务对数据的更新覆盖了。这是因为系统没有执行任何的锁操作，因此并发事务并没有被隔离开来。

脏读

一个事务读取到了另一个事务未提交的数据操作结果。这是相当危险的，因为很可能所有的操作都被回滚。

不可重复读

不可重复读（Non-repeatable Reads）：一个事务对同一行数据重复读取两次，但是却得到了不同的结果。
包括以下情况：
（1） 虚读：事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时得到与前一次不同的值。
（2） 幻读（Phantom Reads）：事务在操作过程中进行两次查询，第二次查询的结果包含了第一次查询中未出现的数据或者缺少了第一次查询中出现的数据（这里并不要求两次查询的SQL语句相同）。这是因为在两次查询过程中有另外一个事务插入数据造成的。

标准SQL规范中，定义了4个事务隔离级别，不同的隔离级别对事务的处理不同。 未授权读取

也称为读未提交（Read Uncommitted）：允许脏读取，但不允许更新丢失。如果一个事务已经开始写数据，则另外一个事务则不允许同时进行写操作，但允许其他事务读此行数据。该隔离级别可以通过“排他写锁”实现。

授权读取

也称为读提交（Read Committed）：允许不可重复读取，但不允许脏读取。这可以通过“瞬间共享读锁”和“排他写锁”实现。读取数据的事务允许其他事务继续访问该行数据，但是未提交的写事务将会禁止其他事务访问该行。

可重复读取（Repeatable Read）

可重复读取（Repeatable Read）：禁止不可重复读取和脏读取，但是有时可能出现幻读数据。这可以通过“共享读锁”和“排他写锁”实现。读取数据的事务将会禁止写事务（但允许读事务），写事务则禁止任何其他事务。

序列化（Serializable）

序列化（Serializable）：提供严格的事务隔离。它要求事务序列化执行，事务只能一个接着一个地执行，不能并发执行。仅仅通过“行级锁”是无法实现事务序列化的，必须通过其他机制保证新插入的数据不会被刚执行查询操作的事务访问到。
隔离级别越高，越能保证数据的完整性和一致性，但是对并发性能的影响也越大。对于多数应用程序，可以优先考虑把数据库系统的隔离级别设为Read Committed。它能够避免脏读取，而且具有较好的并发性能。尽管它会导致不可重复读、幻读和第二类丢失更新这些并发问题，在可能出现这类问题的个别场合，可以由应用程序采用悲观锁或乐观锁来控制。

内存保护

多进程的执行通过内存保护实现互不干扰，如页式管理中有页地址越界保护，段式管理中有段地址越界保护。
内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。通过釆用重定位寄存器和界地址寄存器来实现这种保护。重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址值。每个逻辑地址值必须小于界地址寄存器；内存管理机构动态地将逻辑地址与界地址寄存器进行比较，如果未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。每一个逻辑地址都需要与这两个寄存器进行核对，以保证操作系统和其他用户程序及数据不被该进程的运行所影响。

每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界。如果未越界，则按此地址访问主存，否则将产生程序中断——越界中断（存储保护中断）。

传输层协议 TCP协议

定义：传输控制协议，是面向连接的、可靠的，进程到进程的通信协议。
作用：全双工服务，数据在同一时间传输，数据可以双向传输。
TCP将若干个字节构成一个分组，叫报文段，1500字节为一段。

三次握手

TCP建立连接的过程叫三次握手：客户端向服务器发送了SYN同步请求，请求与服务器建立连接，服务器收到此SYN请求后，会针对客户端SYN同步请求，ACK响应也会发送一个SYN请求，当客户端收到服务器发过来的SYN请求时，会给予一个ACK响应。
因为TCP是一个可靠的传输层协议，它在传输数据前，会建立双向数据通信通道，当保证双向数据传输的通道没有问题时，才会发送数据，起到保护数据的作用。

四次断开

四次断开原理：客户端向服务器发送FIN断开请求，服务器接收到此请求后，回复一个ACK，服务器向客户端发送FIN断开请求，客户吉首到此请求后，回复一个ACK，数据传输的方向是双向的，一个方向的数据通道关闭需要一次请求和确认，因此要断两次，我们有两个方向，所以要断四次

客户机向服务器发送了FIN请求，服务器也给了ACK响应，但是，服务器和客户机之间还有数据要传输，因此，服务器并没有立即向客户机立即发送FIN请求，TCP处于半关闭状态。

UDP协议

UDP协议是无连接、不可靠的传输协议，花费的开销小，速度更快；TCP协议是面向连接的、可靠的传输层协议，有分段、重组、重传等功能，滑动窗口，适用于对可靠性要求较高的场合

排序算法 外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存中，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换。这种排序方法就称为外部排序。

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读 / 写的机械动作所需的时间远远超过内存运算的时间（相对而言可以忽略不记），因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。
外部排序通常采用归并排序法。它包括两个相对独立的阶段：
根据内存缓冲区大小，将外存上的文件分成若干长度为t的子文件，依次读入内存并利用内部排序方法对他们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串。
对这些归并段进行逐趟归并，是归并段逐渐由小到大，直至得到整个有序文件位置。

多路归并排序

外部排序最常用的算法是多路归并排序。
即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。
然后，对已经排序的子文件进行多路归并排序。
假设有一个含10000个记录的文件，首先通过10次内部排序得到10个初始归并段R1～R10 ，其中每一段都含1000个记录。
然后对它们两两归并，直至得到一个有序文件为止。

内排序

内部排序, 指的是待排序记录存放在计算机存储器中进行的排序过程，也就是说用内存就够了。
如果在排序过程中依据不同原则对内部排序方法进行分类，则大致可分为插入排序、冒泡排序、选择排序、归并排序和快速排序等5类。

冒泡排序

重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列）。

原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度

冒泡排序最好的时间复杂度为 O(n)，即有序。
若初始文件是反序的，最坏O(n²)。

稳定性

比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

代码

 public static void bubbleSort(int arr[]) {
        for(int i =0 ; i          
            for(int j=0 ; j  
                if(arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
            	}
            }    
        }
    }

优化

针对问题：
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
方案：
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

快速排序（Quicksort）

对冒泡排序算法的一种改进。

原理

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5）重复第3、4步，直到i == j；如果3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

假设一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此时，ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。
此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。
此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。
此时，i=3，j=7，从第3位往后找，第一个比5大的数是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。
此时，i=4，j=7，从第7位往前找，第一个比5小的数是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。
此时，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序。

// 快速排序
void QuickSort(int arr[], int start, int end)
{
	if (start >= end)
		return;
	int i = start;
	int j = end;
	// 基准数
	int baseval = arr[start];
	while (i < j)
	{
		// 从右向左找比基准数小的数
		while (i < j && arr[j] >= baseval)
		{
			j--;
		}
		if (i < j)
		{
			arr[i] = arr[j];
			i++;
		}
		// 从左向右找比基准数大的数
		while (i < j && arr[i] < baseval)
		{
			i++;
		}
		if (i < j)
		{
			arr[j] = arr[i];
			j--;
		}
	}
	// 把基准数放到i的位置
	arr[i] = baseval;
	// 递归
	QuickSort(arr, start, i - 1);
	QuickSort(arr, i + 1, end);
}

时间复杂度

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n²)。

为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H->r[low].key、H->r[high].key与H->r[(low+high)/2].key，取三者中关键字为中值的元素为中间数。
可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。

选择排序

每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

void SelectionSort(int arr[], int length)
{
    int index, temp;
 
	for (int i = 0; i < length; i++)
	{
        index = i;
		for (int j = i + 1; j < length; j++)
		{
			if (arr[j] < arr[index])
				index = j;
		}
		if (index != i)
		{
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
	}
}

时间复杂度

排序算法的时间复杂度为O(n²)（恒定）。
由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

稳定性

不稳定。

插入排序

插入排序的基本思想就是将无序序列插入到有序序列中。
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。
插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。

例如要将数组arr=[4,2,8,0,5,1]排序，可以将4看做是一个有序序列，将[2,8,0,5,1]看做一个无序序列。无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推，最终数组按照从小到大排序。

代码

// 插入排序
public class Insertion
{
    public static void sort(Comparable[] a)
    {
        //将a[]按升序排列
        int N=a.length;
        for (int i=1;i
        //将a[i]插入到a[i-1]，a[i-2]，a[i-3]……之中
            for(int j=i;j>0&&(a[j].compareTo(a[j-1])<0);j--)
            {
                Comparable temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
}

时间复杂度

当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为 O(n)。
最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n²)。
算法的时间复杂度为O(n²)。
插入排序的空间复杂度为常数阶 O(1)。

稳定性

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。
关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的。

希尔排序

希尔排序(Shell’s Sort)在插入排序算法的基础上进行了改进，算法的时间复杂度与前面几种算法相比有较大的改进。其算法的基本思想是：先将待排记录序列分割成为若干子序列分别进行插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。

代码

// 插入排序
void ShellSort(int arr[], int length)
{
	int increasement = length;
	int i, j, k;
	do
	{
		// 确定分组的增量
		increasement = increasement / 3 + 1;
		for (i = 0; i < increasement; i++)
		{
			for (j = i + increasement; j < length; j += increasement)
			{
				if (arr[j] < arr[j - increasement])
				{
					int temp = arr[j];
					for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement)
					{
						arr[k + increasement] = arr[k];
					}
					arr[k + increasement] = temp;
				}
			}
		}
	} while (increasement > 1);
}

归并排序

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

多路归并就是同时使用更多的归并数量。
设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14；

代码

// 归并排序
void MergeSort(int arr[], int start, int end, int * temp)
{
	if (start >= end)
		return;
	int mid = (start + end) / 2;
	MergeSort(arr, start, mid, temp);
	MergeSort(arr, mid + 1, end, temp);
 
	// 合并两个有序序列
	int length = 0; // 表示辅助空间有多少个元素
	int i_start = start;
	int i_end = mid;
	int j_start = mid + 1;
	int j_end = end;
	while (i_start <= i_end && j_start <= j_end)
	{
		if (arr[i_start] < arr[j_start])
		{
			temp[length] = arr[i_start]; 
			length++;
			i_start++;
		}
		else
		{
			temp[length] = arr[j_start];
			length++;
			j_start++;
		}
	}
	while (i_start <= i_end)
	{
		temp[length] = arr[i_start];
		i_start++;
		length++;
	}
	while (j_start <= j_end)
	{
		temp[length] = arr[j_start];
		length++;
		j_start++;
	}
	// 把辅助空间的数据放到原空间
	for (int i = 0; i < length; i++)
	{
		arr[start + i] = temp[i];
	}
}

效率和稳定性

归并排序比较占用内存，但却是一种效率高且稳定的算法。
改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)

堆排序

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象，可以将堆看做是一个完全二叉树。并且，每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。。
堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

代码

void HeapAdjust(int arr[], int i, int length)
{
	// 调整i位置的结点
	// 先保存当前结点的下标
	int max = i;
	// 当前结点左右孩子结点的下标
	int lchild = i * 2 + 1;
	int rchild = i * 2 + 2;
	if (lchild < length && arr[lchild] > arr[max])
	{
		max = lchild;
	}
	if (rchild < length && arr[rchild] > arr[max])
	{
		max = rchild;
	}
	// 若i处的值比其左右孩子结点的值小，就将其和最大值进行交换
	if (max != i)
	{
		int temp;
		temp = arr[i];
		arr[i] = arr[max];
		arr[max] = temp;
		// 递归
		HeapAdjust(arr, max, length);
	}
}
 
// 堆排序
void HeapSort(int arr[], int length)
{
	// 初始化堆
	// length / 2 - 1是二叉树中最后一个非叶子结点的序号
	for (int i = length / 2 - 1; i >= 0; i--)
	{
		HeapAdjust(arr, i, length);
	}
	// 交换堆顶元素和最后一个元素
	for (int i = length - 1; i >= 0; i--)
	{
		int temp;
		temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
		HeapAdjust(arr, 0, i);
	}
}