全国计算机技术与软件专业技术资格(水平)考试参考用书程序员考试同步辅导(下午科目)(第3版)

第1章 常用算法和数据结构 大纲要求： 排序算法。 查找算法。 数据结构(线性表、栈、队列、数组、树、图)。 1.1 排 序 算 法 1.1.1 考点辅导 1. 选择排序 若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，且任意x∈R[1...i-1]，y∈R[i...n]满足x.key≤y.key，则选择排序的主要思路如下。 (1)反复从R[i...n]中选出关键字*小的结点R[k]。 (2)若i≠k，则将R[i]与R[k]交换，使得R[1...i]有序且保持原来的性质。 (3)i增1，直到i为n。 为方便描述，被查找的顺序表C类型定义如下： #define MAXSIZE 1000 /*顺序表的长度*/ typedef int KeyType; /*关键字类型为整数类型*/ typedef struct{ KeyType key; /*关键字项*/ InfoType otherinfo; /*其他数据项*/ }RecType; /*记录类型*/ typedef struct { RecType r[MAXSIZE+1]; /*r[0]空作为哨兵*/ int length; /*顺序表长度*/ }SqList; /*顺序表类型*/ 顺序存储线性表的选择排序算法如下： void Sqsort(SqList &q) { int i, j, k, temp; for(i=0;i { k=i; for(j=i+1;j if(q.r[j].key if(k!=i) { temp=q.r[k]; q.r[k]=q.r[i]; q.r[i]=temp; } } } 可见，选择排序不管原先序列是否有序，其排序需要比较的次数均为n(n-1)/2；同时，由于相等的两个元素，位置相对在前的可能被交换到后面，故该选择排序是不稳定的。 2. 直接插入排序 若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，则直接插入排序的主要思路如下。 (1)寻找R[i]在R[1…i-1]中的插入位置，确保R[i]插入后保持有序。 (2)i增1，若i小于等于n，则转到(1)执行，否则结束。 顺序线性存储结构下的直接插入排序算法如下： void Dinsert(SqList &q) { int i,j,k; for(i=1;i { for(t=q.r[i],j=i-1;j>=0 && t.key q.r[j+1]=q.r[j]; q.r[j+1]=t; } } 【点评】 (1)对n个结点的线性表采用直接插入排序，当线性表已是从小到大排序时，内循环每执行一次，只需要进行1次比较，整个排序过程只进行n-1次比较。当线性表已是从大到小排序时，对外循环执行i次，内循环要进行i次比较，整个排序过程需要进行n(n-1)/2次比较。可见，对n个结点的线性表采用直接插入排序，*少比较次数为n-1，*多比较次数为n(n-1)/2。 (2)直接插入排序是在有序表的基础上进行的，所以排序效率较高且比较稳定。