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

　　冒泡排序(Bubble Sort)算法分析：

　　先来看看待排序列一趟冒泡的过程：设1

　　通过两两比较、交换，重新安排存放顺序，使得r[j]是序列中关键码最大的记录。一趟冒泡方法为：

　　① i=1; //设置从第一个记录开始进行两两比较

　　② 若i≥j，一趟冒泡结束。

　　③ 比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤

　　④ 当r[i].key>r[i+1].key时， r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];

　　将r[i]与r[i+1]交换

　　⑤ i=i+1; 调整对下两个记录进行两两比较，转②

　　冒泡排序方法：对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n]，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录r[n-1]，如此重复，直到n个记录按关键码有序的表。

　　【算法10.6】

　　① j=n; //从n记录的表开始

　　② 若j<2，排序结束

　　③ i=1; //一趟冒泡，设置从第一个记录开始进行两两比较，

　　④ 若i≥j，一趟冒泡结束，j=j-1;冒泡表的记录数-1，转②

　　⑤ 比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤

　　⑥ 当r[i].key>r[i+1].key时， r[i]<-->r[i+1]; 将r[i]与r[i+1]交换

　　⑦ i=i+1; 调整对下两个记录进行两两比较，转④

　　【效率分析】

　　空间效率：仅用了一个辅助单元。

　　时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。

　　移动次数：

　　最好情况下：待排序列已有序，不需移动。

　　快速排序：

　　快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。

　　【算法10.8】

　　void QSort(S_TBL *tbl,int low,int high) /*递归形式的快排序*/

　　{ /*对顺序表tbl中的子序列tbl->[low…high]作快排序*/

　　if(low

　　{ pivotloc=partition(tbl,low,high); /*将表一分为二*/

　　QSort(tbl,low,pivotloc-1); /*对低子表递归排序*/

　　QSort(tbl,pivotloc+1,high); /*对高子表递归排序*/

　　}

　　}

　　【效率分析】

　　空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度;在最坏情况下，即二叉树是一个单链，为O(n)。

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