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

　　u 快速排序

　　void r_quick(int e[], int low, int high)

　　{ int i, j, t;

　　if(low

　　i=low; j=high; t=e[low];

　　while(i

　　while (it) j--;

　　if(i

　　while (i

　　if(I

　　}

　　e[i]=t;

　　r_quick(e,low,i-1);

　　r_quick(w,i+1,high);

　　}

　　}

　　另外，外排序是对大型文件的排序，待排序的记录存储在外存中，在排序过程中，内存只存储文件的一部分记录，整个排序过程需进行多次的内外存间的交换。

　　直接插入排序算法分析：

　　设有n个记录，存放在数组r中，重新安排记录在数组中的存放顺序，使得按关键码有序。即r[1].key≤r[2].key≤……≤r[n].key

　　先来看看向有序表中插入一个记录的方法：

　　设1

　　【算法10.1】

　　① r[0]=r[j]; //r[j]送r[0]中，使r[j]为待插入记录空位

　　i=j-1; //从第i个记录向前测试插入位置，用r[0]为辅助单元， 可免去测试i<1。

　　② 若r[0].key≥r[i].key，转④。 //插入位置确定

　　③ 若r[0].key < r[i].key时，

　　r[i+1]=r[i];i=i-1;转②。 //调整待插入位置

　　④ r[i+1]=r[0];结束。 //存放待插入记录

　　直接插入排序方法：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。

　　【算法10.2】

　　void InsertSort(S_TBL &p)

　　{ for(i=2;i<=p->length;i++)

　　if(p->elem[i].key < p->elem[i-1].key) /*小于时，需将elem[i]插入有序表*/

　　{ p->elem[0].key=p->elem[i].key; /*为统一算法设置监测*/

　　for(j=i-1;p->elem[0].key < p->elem[j].key;j--)

　　p->elem[j+1].key=p->elem[j].key; /*记录后移*/

　　p->elem[j+1].key=p->elem[0].key; /*插入到正确位置*/

　　}

　　}

　　【效率分析】

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

　　时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。

　　最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较2次移动。

　　总比较次数=n-1次

　　总移动次数=2(n-1)次

　　最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。

　　平均情况下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，移动记录的次数为j/2+2次。

　　由此，直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法。

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