软考软件设计师专题讲义九：数据结构相关算法

　　时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。

　　理想情况下：每次划分，正好将分成两个等长的子序列，则

　　T(n)≤cn+2T(n/2) c是一个常数

　　≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)

　　≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)

　　······

　　≤cnlog2n+nT(1)=O(nlog2n)

　　最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。

　　快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

　　选择排序

　　选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，也即第一趟从n个记录中选取关键码最小的记录，第二趟从剩下的n-1个记录中选取关键码最小的记录，直到整个序列的记录选完。这样，由选取记录的顺序，便得到按关键码有序的序列。

　　简单选择排序：

　　操作方法：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换;第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换;如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。

　　【算法10.9】

　　void SelectSort(S_TBL *s)

　　{ for(i=1;ilength;i++)

　　{ /* 作length-1趟选取 */

　　for(j=i+1，t=i;j<=s->length;j++)

　　{ /* 在i开始的length-n+1个记录中选关键码最小的记录 */

　　if(s->elem[t].key>s->elem[j].key)

　　t=j; /* t中存放关键码最小记录的下标 */

　　}

　　s->elem[t]<-->s->elem[i]; /* 关键码最小的记录与第i个记录交换 */

　　}

　　}

　　从程序中可看出，简单选择排序移动记录的次数较少，但关键码的比较次数依然是

　　堆排序(Heap Sort)：设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。

　　若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点的值是最小(或最大)的。

　　设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆，将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。

　　因此，实现堆排序需解决两个问题：

　　1. 如何将n个元素的序列按关键码建成堆;

　　2. 输出堆顶元素后，怎样调整剩余n-1个元素，使其按关键码成为一个新堆。

　　首先，讨论输出堆顶元素后，对剩余元素重新建成堆的调整过程。

　　调整方法：设有m个元素的堆，输出堆顶元素后，剩下m-1个元素。将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满足堆的性质。将根结点与左、右子女中较小(或小大)的进行交换。若与左子女交换，则左子树堆被破坏，且仅左子树的根结点不满足堆的性质;若与右子女交换，则右子树堆被破坏，且仅右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。称这个自根结点到叶子结点的调整过程为筛选。

　　再讨论对n个元素初始建堆的过程。

　　建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。n个结点的完全

　　子树成为堆，之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总