软件设计师 http://www.educity.cn/jiaocheng/zg7.html
⑧图1-20（a）又是一个n–3个元素的堆，把第一个元素（24）和最后一个元素（05）交换，输出24.这时，如图1-20（b）所示。
图1-20 调整堆的过程之3
⑨在图1-20（b）的基础上，因05小于其左右子结点23和16,则和23交换。交换后，05还是小于其子结点13,和13再交换。如图1-21（a）所示。
⑩图1-21（a）又是一个n–4个元素的堆，把第一个元素（23）和最后一个元素（05）交换，输出23.这时，如图1-21（b）所示。
图1-21 调整堆的过程之4
在图1-21（b）的基础上，因05小于其左右子结点13和16,则和16交换。如图1-22（a）所示。
图1-22（a）又是一个n–5个元素的堆，把第一个元素（16）和最后一个元素（05）
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
交换，输出16.这时，如图1-22（b）所示。
图1-22 调整堆的过程之5
在图1-22（b）的基础上，因05小于其左子结点13,则和13交换，如图1-23（a）所示。
图1-23（a）又是一个n–6个元素的堆，把第一个元素（13）和最后一个元素（05）交换，输出13.这时，如图1-23（b）所示，堆排序过程结束。
图1-23 调整堆的过程之6
堆排序的最坏时间复杂度为O（nlog2n），堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O（1），它是不稳定的排序方法。
1.4.3 交换排序
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
交换排序的基本思想是，两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。 1.冒泡排序
冒泡排序将被排序的记录数组R[1…n]垂直排列，每个记录R[i]看成是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气泡，就使其向上\飘浮\如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 冒泡排序的具体过程如下。
第一步，先比较k1和k2,若k1>k2,则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1和kn.这时最大的排序码记录转到了最后位置，称第一次起泡。共执行n–1次比较。
与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n–2次比较。称第二次起泡。
依此类推，共进行n–1次起泡，完成整个排序过程。
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数为n–1次，记录移动次数为0.因此，冒泡排序最好的时间复杂度为O（n）。
若初始文件是反序的，需要进行n–1趟排序。每趟排序要进行n–i次关键字的比较（1≤i≤n-1），且每次比较都必须移动记录3次来达到交换记录位置的目的。在这种情况下，比较次数达到最大值n（n–1）/2=O（n2），移动次数也达到最大值3n（n–1）/2=O（n2）。因此，冒泡排序的最坏时间复杂度为O（n2）。
虽然冒泡排序不一定要进行n–1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
2.快速排序
快速排序采用了一种分治的策略，通常称其为分治法。其基本思想是，将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程如下。
第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这两组中间。
第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
例如，要对关键码{7,2,5,1,9,6,8,3}进行排序，选择第一个元素为基准。第一趟排序的过程如图1-13所示。
要注意的是，在快速排序中，选定了第一个元素为基准，接着就拿最后一个元素和第一个元素比较，如果大于第一个元素，则保持不变，再拿倒数第二个元素和基准比较；如果小于基准，则进行交换。交换之后，再从前面的元素开始与基准比较，如果小于基准，则保持不变；如果大于基准，则交换。交换之后，再从后面开始比较，依此类推，前后交叉进行。 然后，再采取同样的办法对{3,2,5,1,6}和{8,9}分别进行排序，具体过程如图1-14所示。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
图1-24 第一趟排序过程 图1-25 各趟排序过程
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k–1次关键字的比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须进行n-1次划分，第i次划分开始时区间长度为n–i+1,所需的比较次数为n–i（1≤i≤n-1），故总的比较次数达到最大值n（n-1）/2=O（n2）。如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增次序（或递减次序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。
在最好情况下，每次划分所取的基准都是当前无序区的\中值\记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数为O（nlog2n）。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为O（n2），最好时间复杂度为O（nlog2n）。
尽管快速排序的最坏时间为O（n2），但就平均性能而言，它是基于关键字比较的内